Một số bài tập ứng dụng thuật toán tìm kiếm nhị phân để giải

 MỘT SỐ BÀI TẬP ỨNG DỤNG 
 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN ĐỂ GIẢI 
Bài tập 1: Dãy tổng đối xứng 
 Một dãy các số nguyên không âm A[1], A[2], , A[N] được gọi là dãy tổng 
đối xứng nếu ta có thể tách dãy đó làm 2 dãy có tổng các giá trị bằng nhau. Nghĩa là 
tồn tại một số k trong đoạn [1..N] sao cho tổng A[1] + A[2] + ... + A[k] 
= A[k+1] + A[k+2] + ... + A[N]. 
* Yêu cầu: Cho một dãy gồm N số nguyên không âm. Hãy tìm dãy con gồm các 
phần tử liên tiếp dài nhất mà cũng là dãy tổng đối xứng. 
* Dữ liệu vào: Từ tệp văn bản BAI1.INP có cấu trúc: 
 - Dòng đầu tiên chứa số nguyên N (2 ≤ N≤5000). 
 - N dòng tiếp theo, dòng thứ i trong N dòng chứa giá trị của phần tử A[i] của dãy 
( i = 1, 2, , N). Các số trong dãy không âm và nhỏ hơn 200000 
* Dữ liệu ra: Ghi vào tệp văn bản BAI1.OUT có cấu trúc: 
 Gồm một dòng: Ghi 1 số là độ dài lớn nhất của dãy con gồm các phần tử liên 
tiếp dài nhất là dãy tổng đối xứng. Nếu không có kết quả thì ghi số 0. 
Ví dụ: 
 BAI1.INP BAI1.OUT 
 6 4 
 2 
 10 
 3 
 2 
 5 
 1 
* Ý tưởng 
 Gọi B[i] = A[1]+A[2]++A[i]. Với i = 1, 2, ..., N 
Cần tìm đoạn dài nhất dãy tổng đối xứng. 
- Ta có tổng các phần tử từ vị trí L đến R bằng: B[R]-B[L-1]. L,R:longint; 
 f:text; 
procedure doc; 
var i:longint; 
begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 for i:=1 to n do readln(f,a[i]); 
 fillchar(b,sizeof(b),0); 
 for i:=1 to n do b[i]:=b[i-1]+a[i]; 
 close(f); 
 dodaimax:=0; 
end; 
function np(gt,L,R:longint):boolean; 
var g:longint; 
begin 
 while (L<=R) do 
 begin 
 g:=(L+R) div 2; 
 if b[g]=gt then exit(true); 
 if gt>b[g] then L:=g+1 
 else R:=g-1; 
 end; 
 exit(false); 
end; 
procedure xuly; 
var d,gt:longint; 
begin 
 for d:=n downto 2 do 
 for L:=1 to n-d+1 do 
 begin 
 R:=L+d-1; 
 if (B[L-1]+b[R]) mod 2 = 0 then 
 begin 
 gt:=(b[l-1]+b[r]) div 2; 
 if np(gt,L,R) then 
 begin dodaimax:=d; exit; end; 
 end; 
 end; 
end; 
procedure ghi; 
var i:longint; 
begin 
 assign(f,fo); rewrite(f); 
 i 1 2 3 4 5 6 
 Ai 4 3 7 2 6 4 
 Li 4 3 3 2 2 2 
 Với mỗi vị trí j = 2, 3 .., n ta tìm vị trí i [1, j-1] nhỏ nhất sao cho a[j]-
P L[i]. Khi đó ta được đoạn j-i thỏa mãn điều kiện bài toán, so sánh độ dài đoạn [i,j] 
với phương án tối ưu. 
 Vì 1 ≤ N ≤ 105 , Mảng L là mảng không tăng nên ta có thể áp dụng thuật toán 
tìm kiếm nhị phân trong đoạn [1, j-1] để tìm vị trí i nhỏ nhất sao cho a[j]-P L[i]. Độ 
phức tạp O(NlogN). 
* Cài đặt chương trình 
CONST FI='BAI2.inp'; fo='BAI2.out'; maxn=100000; 
var a,L:array[1..maxn] of longint; 
 n,p,kq:longint; f:text; 
procedure doc;var i:longint; 
begin 
 assign(f,fi); reset(f); 
 readln(f,n,p); 
 for i:=1 to n do read(f,a[i]); 
 close(f); 
end; 
function min(a,b:longint):longint; 
begin 
 if a<b then exit(a) else exit(b); 
end; 
function tknp(i,j:longint):longint; 
var d,c,m,x:longint; 
begin 
 d:=i; c:=j-1;x:=j; 
 while d<=c do 
 begin 
 m:=(d+c) div 2; 
 if L[m]>a[j]-p then d:=m+1 
 else 
 begin 
 x:=m; c:=m-1; 
 end; 
 end; 
 exit(x); 
end; Dữ liệu ra: Ghi vào tệp BAI3.OUT 
 In ra giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai con bò bất kì 
Ví dụ: 
 BAI3.INP BAI3.OUT 
 5 3 3 
 1 
 2 
 8 
 4 
 9 
* Ý tưởng 
 Rất khó để xác định khoảng cách nhỏ nhất giữa hai con bò bất kì là lớn nhất. Ta 
nhận thấy rằng kết quả của bài toán sẽ nằm đâu đó trong đoạn từ 1 đến (xmax - xmin). 
Chính vì vậy ta sẽ tìm kiếm nhị phân theo khoảng cách trong đoạn [1.. xmax - xmin]. 
Với mỗi giá trị khoảng cách K, ta kiểm tra nếu buộc các con bò với khoảng cách nhỏ 
nhất lớn hơn hoặc bằng K có thỏa mãn không (buộc đủ C con bò), nếu thỏa thì ghi 
nhận kết quả hiện tại và thu hẹp không gian tìm kiếm trong đoạn [K+1.. xmax - xmin], 
nếu không thỏa thì tìm trong đoạn [1..K-1]. 
* Cài đặt chương trình 
const fi='BAI3.inp'; fo='BAI3.out'; maxn=100005; 
var f:text; 
 a:array [1..maxn] of int64; 
 n,c:longint; res:int64; ok:boolean; 
procedure nhap; 
var i:longint; 
begin 
 assign(f,fi); 
 reset(f); 
 readln(f,n,c); 
 for i:=1 to n do readln(f,a[i]); 
 close(f); 
end; 
procedure sort(l,r: longint); 
var i,j,x,y: longint; 
begin 
 i:=l; 
 j:=r; end; 
end; 
procedure xuat; 
begin 
 assign(f,fo); 
 rewrite(f); 
 write(f,res); 
 close(f); 
end; 
begin 
 nhap; 
 sort(1,n); 
 chat; 
 xuat; 
end. 
Bài tập 4: Trò chơi với dãy số- Đề thi học sinh giỏi quốc gia năm 2008 
 Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn 
trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: b1, b2, 
..., bn còn dãy số mà bạn thứ hai chọn là c1, c2, ..., cn 
 Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn 
thứ nhất đưa ra số hạng bi(1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì 
giá của lượt chơi đó sẽ là |bi+cj|. 
 Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai 
chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-
2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 
tương ứng với giá của lượt chơi (-2, 2). 
Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có 
thể. 
Dữ liệu vào: Cho trong tệp BAI4.INP gồm: 
 5
 Dòng đầu tiên chứa số nguyên dương n (n ≤ 10 ) 
 9
 Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 10 , i=1, 2, ..., n) 
 9
 Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci| ≤ 10 , i=1, 2, ..., n) 
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. 
Dữ liệu ra : Ghi vào tệp BAI4.OUT 
Ghi ra giá nhỏ nhất tìm được. repeat 
 while a[i]<g do inc(i); 
 while a[j]>g do dec(j); 
 if i<=j then 
 begin 
 tg:=a[i];a[i]:=a[j]; a[j]:=tg; 
 inc(i); 
 dec(j); 
 end; 
 until i>j; 
 if i<R then sx(i,R,a); 
 if L<j then sx(L,j,a); 
end; 
function timnp(k:longint):longint;var L,R,M:longint; 
begin 
 L:=1; 
 R:=n; 
 while L+1R do 
 begin 
 M:=(L+r) div 2; 
 if k>c[m] then L:=m 
 else R:=m; 
 end; 
 if abs(c[L]-k)<abs(C[r]-k) then timnp:=L 
 else timnp:=r; 
end; 
procedure xuly;var i,j:longint; 
begin 
 sx(1,n,b); 
 sx(1,n,c); 
 min:=2000000000; 
 for i:=1 to n do 
 begin 
 j:=timnp(-b[i]); 
 if min>abs(c[j]+b[i]) then 
 min:=abs(c[j]+b[i]); 
 if min=0 then break; 
 end; 
end; 
procedure ghi;var i:longint; 
begin 
 assign(f,fo); rewrite(f); 
 writeln(f,min);