6. Kỹ thuật lùa bò vào chuồng
Ngoài việc dùng kĩ thuật đánh dấu trong khi duyệt, người ta còn hay dùng
kĩ thuật “lùa bò vào chuồng”. Nội dung của kĩ thuật này là: khi duyệt, những
thành phần nào có đặc điểm giống nhau thì lưu vào cùng một chỗ. Kĩ thuật này
có cái tên ngộ nghĩnh như vậy vì quá trình thực hiện tương tự như công việc lùa
những con bò cùng loại vào cùng một chuồng.
Ví dụ xét bài toán: cho mảng A(1..N) một chiều gồm N phần tử là các số nguyên không
âm đánh số từ 1 đến N, có giá trị không vượt quá M, hãy tìm số nguyên không âm nhỏ nhất
chưa có mặt trong mảng A.
Giải bài toán này ta làm như sau: Dùng mảng một chiều B*0..M+1+ để làm vai trò dãy
chuồng bò. Duyệt mảng A[1..N], cho “con bò” A*i+ vào “chuồng” B*j+ với chỉ số j=A*i+, nghĩa là
tăng B*A*i++ lên một đơn vị. Sau đó duyệt lại B theo chỉ số tăng dần từ 0, gặp phần tử đầu
tiên bằng 0 thì chỉ số của phần tử này chính là số nguyên không âm nhỏ nhất chưa có mặt
trong mảng A (loại bò này không có mặt trong đàn bò). Kỹ thuật này có tốc độ tuyến tính
(chỉ cần duyệt mảng A một lần).
Ví dụ 1. Mã nhân viên.
Tổng Giám đốc công ty X nổi tiếng là một người kĩ lưỡng. Ông ta thực hiện việc quản lý
nhân viên của mình bằng cách gán cho mỗi nhân viên một mã số khác nhau. Công ty có N
nhân viên, nhân viên i (i=1, 2, …N) có mã số Ai . Do bận đi công tác nước ngoài một thời gian
dài nên ông trao quyền quản lý công ty cho một người khác. Khi ông trở về, công ty đã có sự
thay đổi về số lượng nhân viên. Khi tiếp nhận thêm nhân viên mới, ông yêu cầu muốn biết
mã số nhỏ nhất có thể gán cho nhân viên mới.
Yêu cầu: Cho N mã số của nhân viên trong công ty. Hãy tìm mã số nhỏ nhất chưa
xuất hiện trong N mã số đã cho
Dữ liệu vào cho trong tệp văn bản MASO.IN: Dòng đầu là số N (1<N 30000). N dòng
tiếp theo, dòng thứ i ghi số Ai (i=1..N; 1 Ai 109)
Kết quả ghi vào tệp văn bản MASO.OUT một số duy nhất là mã số tìm được.
Ví dụ
MASO.IN MASO.OUT
6
7
5
6
1
3
4
2
Phân tích
Đây là bài sử dụng kỹ thuật “lùa bò vào chuồng”.
Văn bản chương trình
const fi='MASO.in';
fo='MASO.out';
var n, k : longint;
b : array[0..30001] of longint;
ai : longint;
Procedure readfile;
var f : text; i : longint;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do b[i] := 0;
for i:=1 to n do begin
read(f,ai);
if ai<=n+1 then inc(b[ai]);
end;
close(f);
end;
Procedure process;
var i : longint;
begin
k := 1;
for i:=1 to n+1 do
if b[i]=0 then begin
k := i;
exit;
end;
end;
Procedure writefile;
var f : text; i : longint;
begin
assign(f,fo); rewrite(f);
writeln(f,k);
close(f);
end;
BEGIN
readfile;
process;
writefile;
END.