Vận dụng thuật toán tìm kiếm nhị phân giải một số bài tập Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA
TRƯỜNG THPT CHUYÊN LAM SƠN
SÁNG KIẾN KINH NGHIỆM
VẬN DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 	 GIẢI MỘT SỐ BÀI TẬP TIN HỌC 
	Người thực hiện: Trịnh Hồng Nam
	Chức vụ: Giáo viên
SKKN thuộc lĩnh vực: Tin học
THANH HÓA NĂM 2016
MỤC LỤC
ĐẶT VẤN ĐỀ
Lý do chọn đề tài
Tìm kiếm là một việc thường xảy ra trong cuộc sống. Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Thuật toán tìm kiếm nhị phân là một trong những thuật toán tìm kiếm quan trọng nhất của tin học. Thuật toán này còn được gọi là thuật toán chặt nhị phân hay thuật toán chia đôi được áp dụng rất nhiều trong giải toán, nó làm giảm được nhiều thời gian tìm kiếm, giúp chương trình chạy nhanh hơn. Tuy nhiên, nhận thấy thuật toán này chưa được áp dụng rộng rãi nên tôi lựa chọn đề tài “Vận dụng thuật toán tìm kiếm nhị phân giải một số bài tập Tin học” để tìm hiểu và phát triển thuật toán phổ biến hơn.
Mục đích nghiên cứu
Trong phạm vi đề tài của mình tôi muốn nghiên cứu một số bài tập tuy không phải mới nhưng khi áp dụng thuật toán tìm kiếm nhị phân thì hiệu quả thuật toán nâng lên rõ rệt, nhằm giúp học sinh hình thành kỹ năng giải bài toán tin học và rèn luyện tư duy thuật toán từ đó rèn luyện tư duy lập trình. Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức. Với bản thân nghiên cứu đề tài sáng kiến kinh nghiệm là cơ hội tốt để nghiên cứu khoa học làm quen với phương pháp làm khoa học tuy chỉ trong phạm vi hẹp nhưng tôi hy vọng cùng với nổ lực của bản thân và sự giúp đỡ của đồng nghiệp sẽ có những đề tài khoa học tốt, lý thú và hiệu quả.
Phạm vi đề tài
Đề tài này được áp dụng đối với học sinh khá và giỏi với nhiệm vụ chủ yếu là ôn thi học sinh giỏi và bồi dưỡng kiến thức cho học sinh yêu thích môn tin.
Phương pháp nghiên cứu
Để hoàn thành đề tài này, tôi đã tiến hành áp dụng một số phương pháp nghiên cứu sau: Phương pháp đặt vấn đề - giải quyết vấn đề, Phương pháp phân tích tổng hợp,Phương pháp so sánh đối chiếu, Phương pháp thực nghiệm.
GIẢI QUYẾT VẤN ĐỀ
Lý thuyết
Nhắc lại thuật toán
Thuật toán tìm kiếm nhị phân liên quan đến bài toán sau:
“ Cho mảng n phần tử đã được sắp tăng dần và một phần tử x. Tìm xem x có trong mảng hay không”
Yêu cầu: Thuật toán này chỉ có thể được dùng khi dãy số được sắp xếp đơn điệu theo thứ tự tăng hoặc giảm dần.
Tư tưởng của thuật toán: chọn phần tử ở vị trí giữa làm chốt, chia dãy thành 2 phần có kích thước nhỏ hơn. Sau đó so sánh phần tử cần tìm x với chốt, nếu x lớn hơn chốt tìm ở nửa sau của dãy, nếu x nhỏ hơn chốt tìm ở nửa trước của dãy (áp dụng với dãy tăng), quá trình trên tiếp tục cho tới khi tìm được x hoặc dãy chia không còn phần tử nào. 
Ví dụ: 
Cho dãy số: A={-6,1,3,5,8,10,14,16,19,21 }; x=5; dãy gồm 10 phần tử 
 Gọi phần tử chốt là k, ban đầu k=8 
 Bước 1: k=8, so sánh x với k, x<k ta tìm kiếm x ở nửa trước {6, 1,3,5,8} 
 Bước 2: k=3, so sánh x với k, x>k ta tìm kiếm x ở nửa sau {3,5,8} 
 Bước 3: k=5, so sánh x với k, x=k ta tìm được x kết thúc. 
Procedure TKNP (x: Item, a1,a2,...,an: Item); 
Begin 
 d := 1; {d là điểm đầu của đoạn tìm kiếm} 
 c := n; {c là điểm cuối của đoạn tìm kiếm} 
 tim_thay:=false;
while (d <=c) and not tim_thay do 
 begin 
 g:= (d+c) div 2 
 if x = a[g] then tim_thay :=true
 else if x<a[g] then c := g-1 
 else d:=g+1
 end 
 If tim_thay then kq:=g
 else kq := 0 {kq là vị trí của số hạng bằng x hoặc 0 nếu không tìm thấy x} 
End;
Độ phức tạp
Để tìm kiếm một phần tử trong mảng. Với cách thông thường, ta phải duyệt tất cả các số từ a[1] đến a[n], tức là mất độ phức tạp O(n). 
Tuy nhiên với mảng đơn điệu, ta dùng chặt nhị phân để tìm kiếm thì :
Ttốt= O(1) ( x nằm ở vị trí giữa mảng)
Txấu= O(logn)
Logarit là một hàm tăng chậm. Trong trường hợp ta còn băn khoăn về tính hiệu quả khi tìm kiếm nhị phân, hãy xét việc tìm kiếm một tên trong một cuốn danh bạ điện thoại có chứa một triệu tên. Tìm kiếm nhị phân cho phép ta tìm thấy bất kỳ tên nào chỉ sau nhiều nhất 21 lượt so sánh. Nếu ta có thể quản lý một danh sách có chứa tất cả mọi người trên thế giới được sắp xếp theo tên, ta có thể tìm thấy bất kỳ người nào trong vòng chưa đầy 35 bước.  
Bài tập
Phần bài tập cơ bản
Bài 1. ĐOÁN SỐ
Hai người chơi như sau: Người thứ nhất sẽ nghĩ ra một số nguyên dương trong khoảng từ 1 đến N (N được cho biết trước). Người thứ hai sẽ lần lượt đưa ra các số dự đoán. Với mỗi số dự đoán này, người thứ hai sẽ nhận được câu trả lời cho biết số mình vừa nêu ra lớn hơn, nhỏ hơn, hay bằng với số mà người thứ nhất đã nghĩ. Em hãy giúp người thứ hai chọn đúng số cần tìm với số lần đoán càng ít càng tốt.
Thuật toán:
Người thứ hai muốn chọn đúng số mà người thứ nhất nghĩ với số lần đoán ít nhất thì người thứ hai chắc chắn phải sử dụng đến thuật toán tìm kiếm nhị phân. Các bước sẽ lần lượt như sau:
Bước 1.X:=1; y:=n; a:=0;
Bước 2.A:=(x+y) div 2
Bước 3.Lần đoán thứ i: a
Bước 4.Nếu a lớn hơn số cần tìm thì gán y:=a
Nếu a nhỏ hơn số cần tìm thì gán x:=a
Bước 5.Nếu số lần đoán vượt quá log2N thì chấm dứt
Ngược lại thì trở lại bước 2
Bài 2. BÀI TOÁN CỔ
"Vừa gà vừa chó
Bó lại cho tròn
Ba mươi sáu con
Một trăm chân chẵn
Hỏi có bao nhiêu gà bao nhiêu chó?"
Bài toán này các em đều đã rất quen thuộc từ hồi học cấp I. Phương pháp để giải bài toán này là phương pháp giả thiết tạm. 
Tất cả có 36 con vật. Chúng không thể đều là gà vì như vậy sẽ chỉ có 72 chân. Cũng không thể nào là chó cả vì như vậy sẽ có cả thảy 144 chân (Số chân của chúng là 100 chân). 
Áp dụng tư tưởng chặt nhị phân cho bài toán này như sau:
- Sắp xếp số gà theo thứ tự tăng dần (theo chiều từ dưới lên)
- Chia đôi tổng số gà, nếu tại điểm giữa đó tổng số chân gà và chân gà và chân chó lớn hơn 100 thì lấy nửa trên, và ngược lại lấy nửa dưới.
Thuật toán:
1. d:=0; c:=36; x:=100;
2.Trong khi d<c thì 
 	2.1.g:= (d+c) div 2;
2.2.Nếu x=2*g+4*(36-g) thì
y:=c-g; Số gà là g; Số chó là y
2.3.Nếu x>2*g+4*(36-g) thì c:=g
2.4Nếu x<2*g+4*(36-g) thì d:=g
3.Quay lại bước 2
4.Kết thúc.
Bài 3. SỐ 0 CUỐI CÙNG
Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong dãy.
Thuật toán:
Ta tiến hành tìm kiếm nhị phân trên xâu kí tự để tìm ra vị trí số 0 cuối cùng như sau:
 - Tìm phần tử giữa xâu đang xét
So sánh kí tự ở vị trí giữa xâu với kí tự 0.
Nếu kí tự giữa xâu là kí tự 0 thì ta tìm ở nửa sau của xâu, nếu không phải kí tự 0 (mà là 1) thì ta tìm ở nửa trước của xâu.
 1.d:=1; c:=length(s);
 2. trong khi d<c thì 
 2.1 g:=(d+c+1) div 2;
 2.2 Nếu s[g]='0' thì d:=g 
 2.3 Nếu s[g]='1' thì c:=g-1;
 3.Quay lại bước 3
4.Kết thúc
Vậy vị trí của số 0 cuối cùng trong dãy là d
Bài 4. TÌM N
Tìm số nguyên dương n thỏa mãn hệ thức : C12n+ C32n +.+C2n-12n =2048 
(Ckn là tổ hợp chập k của n phần tử)
Ta biết rằng C12n+ C32n +.+C2n-12n =2048 thì n≤ 8 vì nếu n >8 thì
C52.8 =C516 = (12.13.14.15.16)/(1.2.3.4.5)= 13.7.3.16=4368 > 2048 
Thuật toán:
d=0;c= 8; x=2048;
trong khi d<c thì
2.1.g:=(d+c) div 2;
2.2. nếu x=Tong(g) ( tong(g)= C12g+ C32g +.+Cg-12g) thì
 Xuất ra số cần tìm là g
2.3.Nếu (x>tong(g)) thì l:=g
2.4.Nếu (x<tong(g)) thì r:=g
Quay lại bước 2
Kết thúc
Chắc chắn là trước khi áp dụng thuật toán tìm kiếm nhị phân để tìm N ta phải xây dựng một hàm tính giai thừa của một số nguyên, một hàm tính tổ hợp theo công thức Ckn=n!/(k!*(n-k)!)
Bài 5. HÀNG CÂY
Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có N cây, mỗi cây có độ cao là a1, a2,aN.
Người ta cần lấy M mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao H (mét) để cưa tất cả các cây có độ cao lớn hơn H (dĩ nhiên những cây có độ cao không lớn hơn H thì không bị cưa). 
Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là 20; 15; 10 và 18 mét, cần lấy 7 mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng là 15; 15; 10 và 15 mét. Tổng số mét gỗ lấy được là 8 mét (dư 1 mét).
Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên H lớn nhất) sao cho lấy được M mét gỗ và số mét gỗ dư ra là ít nhất.
Dữ liệu: 
Dòng thứ nhất chứa 2 số nguyên dương N và M (1≤N≤106; 1≤M≤2x109) cách nhau một dấu cách.
Dòng thứ hai chứa N số nguyên dương ai là độ cao của mỗi cây trong hàng (1≤ai≤109; i=1N), mỗi số cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra màn hình một số nguyên cho biết giá trị cần tìm.
Ví dụ:
WOOD.INP
WOOD.OUT
4 7
20 15 10 18
15
Thuật toán :
+ Đầu=0, cuối= chiều cao cây cao nhất.
+ Kiểm tra số mét gỗ S lấy được khi chặt ở độ cao h=(đầu+cuối) div 2:
- Nếu S=M: Thì in ra h và dừng chương trình.
- Nếu S<M thì đầu =h
- Nếu S>M thì cuối =h
- Tiếp tục kiểm tra h cho đến khi chênh lệch của M,S lặp lại.
Phần nâng cao
Trong thực tế, ta thường gặp dạng bài toán tìm thời điểm kết thúc sớm nhất (hay muộn nhất) của một công việc, tìm chi phí bé nhất (hay lớn nhất), với các yêu cầu ràng buộc trong đề bài. Khi đó ta nghĩ đến một thuật toán rất hiệu quả - thuật toán tìm kiếm nhị phân. 
Sau đây là một số bài tập trong các đề thi học sinh giỏi
Bài 6. CHỈNH DÃY SỐ
Cho một dãy N (N≤2x105) số nguyên dương không quá 109. Có thể giữ nguyên hoặc bỏ không quá một đoạn liên tiếp các số trong dãy. Hãy thực hiện một trong hai cách trên sao cho dãy số thu được có độ dài đoạn liên tiếp tăng dần là lớn nhất.
Ví dụ : với dãy 1 2 3 1 4 5 sẽ chỉ có cách bỏ số 1 thứ 2 trong dãy đi để thu được dãy mới có độ dài đoạn con liên tiếp tăng dần là 5
Với dãy 1 3 4 6 ta không cần bỏ số nào đi
Dữ liệu vào từ file DEFENSE.INP
- Dòng 1 : số nguyên T≤25 là số bộ test
- T nhóm dòng sau: mỗi nhóm gồm 2 dòng. Dòng đầu ghi số nguyên N, dòng sau ghi N số nguyên là các số trong dãy theo thứ tự từ trái qua phải
Kết quả ghi ra flie DEFENSE.OUT chứa độ dài đoạn con liên tiếp tăng dần lớn nhất có thể thu được.
DEFENSE.INP
DEFENSE.OUT
2
9
5 3 4 9 2 8 6 7 1
7
1 2 3 10 4 5 6
4
6
 Ví dụ : 
Thuật toán :
Gọi L[i] là độ dài dãy dài nhất các số liên tiếp tăng dần kết thúc tại A[i]
 R[i] là độ dài dãy dài nhất các số liên tiếp tăng dần bắt đầu tại A[i]
R và L tính được nhờ thuật toán quy hoạch động. Ta phải tìm giá trị cực đại của tổng L[i]+R[j] sao cho i ≤ j và A[i]<A[j].
Xét hàm Find(L,R) để tìm giá trị Max của L[i]+R[j] với A[i]<A[j] và L≤ i <j≤ R.
Ta chia đoạn [L,R] thành hai đoạn con [L,m] và [m+1,R] với m=(L+R) div 2. 
Xét trường hợp :
+ Nếu i và j cùng thuộc một trong hai đoạn con này, giá trị max của L[i]+R[j] có thể tính được nhờ thủ tục find(L,m) và find(m+1,R).
+ Nếu i thuộc đoạn con thứ nhất và j thuộc đoạn con còn lại, ta áp dụng Merge sort để sắp xếp lại các A trong đoạn từ [L,R] tăng dần sau mỗi lần gọi find(L,R).
Từ đó với mỗi iÎ[L,m] ta có thể tìm kiếm nhị phân ra jÎ[m+1,R] tương ứng sao cho A[j] nhỏ nhất lớn hơn A[i] và tìm ra được giá trị lớn nhất của tổng L[i]+R[i] 
Bài 7. CĂN N
 Biết rằng căn bậc N của một số S là một sốnguyên <106. Tìm căn bậc N của S
CANN.INP
CANN.OUT
4
81
3
Dữ liệu vào: file CANN.INP 
Dòng 1 là số N (N ≤ 100)
Dòng 2 là số S(0 ≤ S ≤ 10100 )
Kết quả ra: file CANN.OUT 
Gồm 1 dòng duy nhất là căn bậc N của số S.
Thuật toán:
 - Cmin =0; Cmax = 106.Kết quả sẽ nằm trong đoạn [Cmin ,Cmax ].
- Đặt Ctg =(Cmin +Cmax )div 2. Tính A= CTG N. Để tính A ta dùng thuật toán nhân sốlớn.
 Nếu A > S thì tìm kiếm trong đoạn [Ctg+1 ,Cmax ]
 Nếu A < S thì tìm kiếm trong đoạn [ Cmin , C tg -1 ]
 Nếu A=S thì căn bậc N của S chính là Ctg 
- Tiếp tục tìm kiếm cho tới khi Cmin >Cmax 
Cài đặt:
Bài 8. Dãy con tăng dài nhất 
Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.
Input: File Lis.Inp
Dòng đầu tiên gồm số nguyên N.
Dòng thứ hai gồm N số mô tả dãy.
Output: file Lis.Out Gồm một số nguyên duy nhất là đáp số của bài toán
Lis.Inp
Lis.Out
5
2 1 4 3 5
3
Ví dụ:
Thuật toán:
Gọi k là độ dài cực đại của dãy con tăng và ký hiệu H[1..k] là dãy có ý nghĩa sau: H[i] là số hạng nhỏ nhất trong các số hạng cuối cùng của các dãy con tăng có độ dài i. Đuơng nhiên h[1] < h[2] <.. < h[k]. Mỗi khi xét thêm một giá trị mới trong dãy A thì các giá trị trong dãy H và giá trị k cũng tương ứng thay đổi. 
Bài 9. YUGI 
Các bạn đã đọc bộ truyện tranh Nhật Bản Yugi-oh chắc hẳn ai cũng cực kì yêu thích trò chơi bài Magic. Bộ bài và chiến thuật chơi quyết định đến sự thắng thua của đối thủ(mà sự thắng thua thì còn liên quan đến cả tính mạng). Vì thế tầm quan trọng của bộ bài là rất lớn. Một bộ bài tốt không chỉ bao gồm các quân bài mạnh mà còn phụ thuộc vào sự hỗ trợ tương tác giữa các quân bài. Bộ bài của Yugi là một bộ bài có sự bổ sung, hỗ trợ cho nhau rất tốt, điều này là 1 trong các nguyên nhân khiến Kaiba luôn là kẻ chiến bại.
Tình cờ Kaiba đã tìm được 1 quân bài ma thuật mà chức năng của nó là chia bộ bài hiện có của đối thủ ra làm K phần, mỗi phần có ít nhất 1 quân bài (điều này làm giảm sức mạnh của đối thủ). Kaiba quyết định áp dụng chiến thuật này với Yugi. Hiện tại Yugi có trong tay N quân bài, 2 quân bài i, j có sức mạnh tương tác a(i,j) (a(i,j) = a(j,i)). Kaiba muốn chia các quân bài thành K phần theo quy tắc sau:
Giả sử K phần là P1, P2, ..., Pk thì độ giảm sức mạnh giữa 2 phần u,v là b(u,v) = min(a(i,j) với i thuộc Pu, j thuộc Pv).
Độ giảm sức mạnh của bộ bài là S = min(b(u,v) với 1 ≤ u, v ≤ K).
yugi.Inp
yugi.Out
4 3
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0
2
Kaiba muốn chia K phần sao cho S lớn nhất
Input: file yugi.inp 
Dòng đầu là 2 số N,K(2 ≤ K ≤ N ≤ 200)
N dòng tiếp theo mỗi dòng là N số a(i,j) (a(i,j) ≤ 32767; nếu i = j thì a(i,j) = 0)
Output: file yugi.out gồm 1 dòng duy nhất là S lớn nhất
Thuật toán : 
Chặt nhị phân, với mỗi giá trị V(sức mạnh) đang xét, nhóm tất cả các quân bài (i,j) thành 1 nhóm nếu 
 + i ≠ j. 
 + a[i,j] <= V. 
Để phân nhóm có thể sử dụng BFS. 
Kiểm tra xem liệu số nhóm cần thiết để có giá trị V là bao nhiêu ? Nhỏ hơn K hay lớn hơn K , từ đó giảm dần khoảng cần xét .
Bài 10. MTWALK 
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.
MTWALK.INP
MTWALK.OUT
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
2
Dữ liệu: File MTWALK.INP
Dòng 1: N
Dòng 2..N+1: Mỗi dòng chứa N số nguyên, mỗi số cho biết cao độ của một ô.
Kết quả: File MTWALK.OUT gồm một số nguyên là chênh lệch cao độ nhỏ nhất.
Thuật toán : 
Ta có nhận xét các giá trị độ cao nằm trong khoảng [1,110], vì thế ta có thuật toán chặt nhị phân như sau : 
Giả sử ta đang xét giá trị V ( Chênh lệch chiều cao) 
 - Vì chênh lệch tối ưu đang xét là V, suy ra nếu giá trị chiêù cao nhỏ nhất trong đường đi tìm được là Min, thì giá trị chiều cao lớn nhất phải nhỏ hơn hoặc bằng Max = Min + V. 
 - Do chiều cao các ô <=110, nên việc thử lần lượt các giá trị dưới (giá trịMin) có thể chạy trong thời gian cho phép . 
 -Với mỗi giá trị V, ta tiến hành loang để tìm một đường đi thỏa mãn 2 điều kiện trên. Độ phức tạp M log M * N^2 ( M là giá trị) 
Bài 11. TẢI TRỌNG TUYẾN ĐƯỜNG 
Một hệ thống giao thông liên thông gồm N thành phố với tên 1..N (N <= 100). Có một số đoạn đường hai chiều giữa một số cặp thành phố và mỗi đoạn đường có một tải trọng tối đa mà chỉ có các xe với tải trọng không lớn hơn mới đi qua được. Cần đi từ thành phố U tới V. Hãy tìm một hành trình sao cho tải trọng tối đa cho phép trên hành trình đó là lớn nhất có thể được. 
Dữ liệu : Trong file văn bản TAITRONG.INP gồm 
- Dòng đầu là 3 số N, U, V 
- Tiếp theo là một số dòng, mỗi dòng ghi ba số nguy n d ng X Y Z với ý nghĩa có đường đi giữa X và Y với tải trọng tối đa cho phép là Z (0 < Z <= 10000). 
 Kết quả : Ra file văn bản TAITRONG.OUT gồm 
- Dòng thứ nhất ghi tải trọng H tối đa của xe có thế. 
- Trong các dòng tiếp, mỗi dòng ghi tên một thành phố trong hành trình từ U kết thúc tại V. 
Ví dụ :
TAITRONG.INP
TAITRONG.OUT
4 1 4 
1 2 10 
2 4 1 
1 3 5 
3 4 3
3 
1 
3 
4
Thuật toán
 
 
Đặt Hmin = Min(a[i, j]), Hmax = Max(a[i, j]). Với mỗi giá trị h (Hmin ≤ h ≤ Hmax) ta xây dựng đồ thị G(h) thỏa mãn:
 - N đỉnh tương ứng với N thành phố. 
 - 2 đỉnh i, j có cạnh nối nếu a[i, j] ≥ h. 
Như vậy, nếu ta tìm thấy được một đường đi từ U tới V thì ta nói rằng : "Mạng giao thông có tải trọng tối thiểu h". Bài toán trở thành "Tìm giá trị h lớn nhất để tồn tại đường đi từ U tới V". 
Ta sẽ sử dụng tìm kiếm nhị phân dựa theo nhận xét: Nếu mạng có tải trọng tối thiểu k, và h là giá trị lớn nhất để "mạng giao thông có tải trọng tối thiểu h" thì k ≤ h ≤ Hmax. Ngược lại, nếu không có lộ trình với tải trọng tối thiểu là k thì Hmin ≤ h< k. 
Với mỗi giá trị h, có thể duyệt DFS hoặc BFS để kiểm tra tồn tại đường đi từ U tới V hay không.
Bài 12. ĐIỀU ĐỘNG 
Sau khi thực thi quy hoạch của Bộ Giao thông, sơ đồ giao thông của thành phố H gồm n tuyển đường ngang và n tuyến đường dọc cắt nhau tạo thành một lưới ô vuông với n x n nút giao thông. Các nút giao thông được gán tọa độ theo hàng từ 1 đến n, từ trên xuống dưới và theo cột từ 1 đến n, từ trái sang phải. Ban chỉ đạo an toàn giao thông quyết định điều n cảnh sát giao thông đến các nút giao thông làm nhiệm vụ. Ban đầu mỗi cảnh sát được phân công đứng trên một nút của một tuyến đường ngang khác nhau. Đến giờ cao điểm, xuất hiện ùn tắc tại các tuyến đường dọc không có cảnh sát giao thông. Để sớm giải quyết tình trạng này, Ban chỉ đạo an toàn giao thông quyết định điều động một số cảnh sát giao thông ở một số nút, từ nút hiện tại sang một nút khác cùng hàng ngang để đảm bảo mỗi tuyến đường dọc đều có mặt của cảnh sát giao thông.
Yêu cầu: Biết rằng cảnh sát ở hàng ngang thứ i cần ti đơn vị thời gian để di chuyển qua 1 cạnh của lưới ô vuông (i = 1, 2, ..., n), hãy giúp Ban chỉ đạo an toàn giao thông tìm cách điều động các cảnh sát thỏa mãn yêu cầu đặt ra sao cho việc điều động được hoàn thành tại thời điểm sớm nhất. Giả thiết là các cảnh sát được điều động đồng thời thực hiện việc di chuyển đến vị trị mới tại thời điểm 0.
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.
Dữ liệu vào từ file MOVE.INP
Dòng thứ nhất chứa một số nguyên dương n (n ≤ 10000).
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương ci, ti (ti ≤ 10000) tương ứng là tọa độ cột và thời gian để di chuyển qua 1 cạnh của lưới ô vuông của cảnh sát đứng trên tuyến đường ngang thứ i (i = 1, 2, ..., n).
Hai số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả ghi ra file MOVE.OUT
Ghi ra một số nguyên duy nhất là thời điểm sớm nhất tìm được.
Ví dụ:
MOVE.INP
MOVE.OUT
5
5 10
3 10
3 20
2 9
2 15
10
Thuật toán:
Với yêu cầu của bài toán, ta nhận thấy cần áp dụng thuật toán tìm kiếm nhị phân. Ta phải giải quyết một bài tập đơn giản hơn là kiểm tra xem trong thời gian t, các cảnh sát có thể di chuyển đến các vị trí thỏa mãn yêu cầu đề bài hay không.
Với khoảng thời gian t cho trước, mỗi cảnh sát i có thể di chuyển đến các cột trong khoảng [li, ri] nào đó. Ta có nhận xét rằng trong các cách chọn đúng, tồn tại một cách chọn mà ở đó cảnh sát đi đến cột 1 là cảnh sát có ri nhỏ nhất trong các cảnh sát có thể đến cột 1.
Thật vậy, xét một cách chọn đúng, cảnh sát đi đến cột 1 là j và có rj>ri còn cảnh sát sẽ đi đến cột k, ta có lj= li=1; k≤ ri<rj. Do đó ta có thể đổi lại là cảnh sát i đến cột 1 còn cảnh sát j đến cột k. Việc chọn cảnh sát tiếp theo để đi đến các cột 2,3,, n cũng tương tự như vậy. 
Thuật toán sẽ là xét lần lượt các cột từ 1 đến n, khi đến cột i, trong các cảnh sát chưa được chọn và đến được cột i, cảnh sát có r tương ứng nhỏ nhất sẽ được chọn để đến cột i. Dùng heap để quản lý được các cảnh sát đến được cột hiện tại