Tìm kiếm nhị phân theo đáp án

Mức độ: Nâng cao

Tìm kiếm nhị phân thường được học để tìm một số trong dãy đã sắp xếp. Nhưng ý tưởng “chia đôi khoảng tìm kiếm” dùng được cho một loại bài rộng hơn nhiều: đề hỏi giá trị nhỏ nhất (hoặc lớn nhất) thỏa mãn một điều kiện, mà tìm thẳng giá trị đó thì khó, còn kiểm tra một giá trị cho trước có thỏa mãn không thì dễ. Khi đó ta đoán đáp án, kiểm tra, rồi thu hẹp khoảng đoán đi một nửa.

Ví dụ: chia sách

Có n cuốn sách xếp thành hàng, cuốn thứ i dày a_i trang. Chia hàng sách thành k đoạn liên tiếp cho k bạn đọc. Bạn phải đọc nhiều nhất càng ít càng tốt: số trang lớn nhất mà một bạn phải đọc nhỏ nhất là bao nhiêu?

Tìm thẳng cách chia tốt nhất thì khó. Nhưng câu hỏi ngược lại dễ hơn nhiều: “nếu mỗi bạn đọc không quá x trang thì có chia được không?” Trả lời bằng tham lam: cho bạn thứ nhất nhận sách từ đầu hàng, nhận thêm khi tổng còn không quá x; không nhận được nữa thì chuyển sang bạn tiếp theo. Đếm số bạn cần, nếu không quá k thì chia được.

Gọi chia_duoc(x) là câu trả lời. Hàm này có tính chất quan trọng: x chia được thì mọi số lớn hơn x cũng chia được (cho phép mỗi bạn đọc nhiều hơn thì càng dễ chia). Vậy khi đi x từ nhỏ đến lớn, câu trả lời có dạng:

x	10	11	12	13	14	15	16
chia_duoc(x)	không	không	không	có	có	có	có

Đáp án là vị trí đầu tiên chuyển từ “không” sang “có”. Tìm vị trí này bằng tìm kiếm nhị phân: thử ở giữa khoảng, nếu “có” thì đáp án ở nửa trái (gồm cả điểm giữa), nếu “không” thì ở nửa phải.

Với sách dày 7 2 5 10 8 và k = 2:

Khoảng [thap, cao]	giữa	chia_duoc(giữa)	Khoảng mới
[10, 32]	21	có: 7 2 5 | 10 8	[10, 21]
[10, 21]	15	không: cần 3 bạn	[16, 21]
[16, 21]	18	có: 7 2 5 | 10 8	[16, 18]
[16, 18]	17	không: 7 2 5 | 10 | 8	[18, 18]

Đáp án 18. Khoảng ban đầu: x không thể nhỏ hơn cuốn dày nhất (10), và x bằng tổng mọi cuốn (32) thì chắc chắn chia được.

Python

n, k = map(int, input().split())
a = list(map(int, input().split()))

def chia_duoc(x):
    so_ban, dang_doc = 1, 0
    for trang in a:
        if dang_doc + trang > x:      # bạn hiện tại không nhận thêm được
            so_ban += 1
            dang_doc = 0
        dang_doc += trang
    return so_ban <= k

thap, cao = max(a), sum(a)
while thap < cao:
    giua = (thap + cao) // 2
    if chia_duoc(giua):
        cao = giua                    # giua thỏa mãn: đáp án là giua hoặc nhỏ hơn
    else:
        thap = giua + 1               # giua không thỏa mãn: đáp án lớn hơn giua
print(thap)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<long long> a;

bool chiaDuoc(long long x) {
    int soBan = 1;
    long long dangDoc = 0;
    for (long long trang : a) {
        if (dangDoc + trang > x) {   // bạn hiện tại không nhận thêm được
            soBan++;
            dangDoc = 0;
        }
        dangDoc += trang;
    }
    return soBan <= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (auto &x : a) cin >> x;
    long long thap = *max_element(a.begin(), a.end()), cao = 0;
    for (long long x : a) cao += x;
    while (thap < cao) {
        long long giua = (thap + cao) / 2;
        if (chiaDuoc(giua)) cao = giua;   // đáp án là giua hoặc nhỏ hơn
        else thap = giua + 1;             // đáp án lớn hơn giua
    }
    cout << thap << "\n";
    return 0;
}

Mỗi lần kiểm tra mất n bước, khoảng tìm kiếm dài S (tổng số trang) nên cần khoảng log₂S lần kiểm tra. Với n = 10⁵ và S = 10¹⁴, cả bài khoảng 47 × 10⁵ bước.

Khuôn mẫu chung

1. Đặt câu hỏi có/không kiem_tra(x): “đáp án không quá x có được không?” (hoặc “ít nhất x”).
2. Chứng minh tính đơn điệu: x thỏa mãn thì mọi x lớn hơn (hoặc nhỏ hơn) cũng thỏa mãn. Không có tính chất này thì không dùng được tìm kiếm nhị phân.
3. Chọn khoảng [thap, cao] chắc chắn chứa đáp án.
4. Thu hẹp cho đến khi thap = cao.

Đề hỏi	Kiểm tra	Thu hẹp
x nhỏ nhất thỏa mãn	thỏa mãn thì cao = giua, không thì thap = giua + 1	giua = (thap + cao) // 2
x lớn nhất thỏa mãn	thỏa mãn thì thap = giua, không thì cao = giua - 1	giua = (thap + cao + 1) // 2

Lưu ý: khi tìm x lớn nhất phải làm tròn lên (cộng 1 trước khi chia đôi). Nếu làm tròn xuống, với thap = 5, cao = 6 thì giua = 5, thỏa mãn thì thap = giua = 5, khoảng không đổi và vòng lặp chạy mãi không dừng.

Tìm kiếm nhị phân trên số thực

Khi đáp án là số thực, khoảng không bao giờ thu về đúng một điểm. Thay vì while thap < cao, chỉ cần lặp một số lần cố định, ví dụ 100 lần: mỗi lần khoảng giảm một nửa, sau 100 lần còn 1 / 2¹⁰⁰ độ dài ban đầu, nhỏ hơn rất nhiều so với sai số cần in ra.

thap, cao = 0.0, 1e9
for _ in range(100):
    giua = (thap + cao) / 2
    if kiem_tra(giua):
        cao = giua
    else:
        thap = giua
print(f"{thap:.6f}")

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Tìm nhị phân trên số nguyên

Bài 1. Căn bậc hai nguyên

Nhập n (0 ≤ n ≤ 10¹⁸). In ra số nguyên x lớn nhất mà x × x ≤ n.

Ví dụ: nhập 50 thì in ra 7.

Kiểm tra: nhập 999999999999999999.

Xem đáp số

999999999

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Xếp hình tam giác

Có n viên bi (1 ≤ n ≤ 10¹⁸). Xếp thành tam giác: hàng 1 có 1 viên, hàng 2 có 2 viên, …, mỗi hàng phải đủ số viên. In ra số hàng nhiều nhất xếp được.

Ví dụ: nhập 20 thì in ra 5.

Kiểm tra: nhập 123456789012345678.

Xem đáp số

496903992

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Căn bậc ba nguyên

Nhập n (0 ≤ n ≤ 10¹⁸). In ra số nguyên x lớn nhất mà x × x × x ≤ n.

Ví dụ: nhập 1000 thì in ra 10.

Kiểm tra: nhập 987654321987654321.

Xem đáp số

995867

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Giai thừa có k chữ số 0

Nhập k (1 ≤ k ≤ 10¹²). In ra số tự nhiên n nhỏ nhất sao cho n! có ít nhất k chữ số 0 ở tận cùng.

Ví dụ: nhập 6 thì in ra 25.

Kiểm tra: nhập 100000.

Xem đáp số

400005

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Kiểm tra bằng cách đếm

Bài 5. Máy photo

Có n máy photo, máy thứ i photo một bản mất t_i giây, các máy chạy cùng lúc. Cần k bản. Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁹), dòng thứ hai có n số t_i (1 ≤ t_i ≤ 10⁹). In ra số giây ít nhất để có đủ k bản.

Ví dụ:

Nhập	In ra
2 5 3 5	10

Kiểm tra: nhập

5 1000000000
7 3 1000000000 12 5

Xem đáp số

1316614420

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Cắt gỗ

Có n khúc gỗ, khúc thứ i dài a_i mét. Cần cắt ra ít nhất k đoạn có cùng độ dài L mét (L nguyên dương), phần thừa bỏ đi, không được nối gỗ. Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁹), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁹). In ra L lớn nhất, hoặc 0 nếu không cắt được.

Ví dụ:

Nhập	In ra
4 11 802 743 457 539	200

Kiểm tra: nhập

6 25
120 75 300 18 260 99

Xem đáp số

32

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Ăn kẹo

Có n hộp kẹo, hộp thứ i có a_i viên. Mỗi giờ bạn Na chọn một hộp và ăn tối đa v viên trong hộp đó (hộp còn ít hơn v viên thì ăn hết hộp, giờ đó không ăn thêm hộp khác). Na phải ăn hết kẹo trong h giờ. Dòng đầu có n, h (1 ≤ n ≤ h ≤ 10⁹, n ≤ 10⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁹). In ra v nhỏ nhất.

Ví dụ:

Nhập	In ra
4 8 3 6 7 11	4

Kiểm tra: nhập

5 20
30 11 23 4 20

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số thứ k trong bảng nhân

Bảng nhân có n hàng, m cột, ô ở hàng i cột j ghi số i × j. Viết hết n × m số ra và sắp xếp tăng dần (giữ cả số trùng). Dòng duy nhất có n, m, k (1 ≤ n, m ≤ 10⁵, 1 ≤ k ≤ n × m). In ra số thứ k.

Ví dụ: nhập 3 3 5 thì in ra 3.

Kiểm tra: nhập 1000 2000 1234567.

Xem đáp số

531360

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số thứ k chia hết cho a hoặc b

Nhập a, b, k (1 ≤ a, b ≤ 10⁹, 1 ≤ k ≤ 10⁹). Xét các số nguyên dương chia hết cho a hoặc chia hết cho b, xếp tăng dần. In ra số thứ k.

Ví dụ: nhập 4 6 5 thì in ra 16.

Kiểm tra: nhập 123456 654321 1000000000.

Xem đáp số

103860316030464

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Số thứ k của hai dãy

Dòng đầu có n, m, k (1 ≤ n, m ≤ 10⁵, 1 ≤ k ≤ n + m). Dòng thứ hai có n số nguyên không giảm, dòng thứ ba có m số nguyên không giảm (|giá trị| ≤ 10⁹). Gộp hai dãy và sắp xếp tăng dần, in ra số thứ k.

Ví dụ:

Nhập	In ra
3 4 4 1 5 9 2 3 8 10	5

Kiểm tra: nhập

5 5 7
-100 -5 0 0 77
-50 0 3 1000000000 1000000000

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Kiểm tra bằng tham lam

Bài 11. Xe chở hàng

Có n kiện hàng xếp theo thứ tự, kiện thứ i nặng w_i kg. Mỗi ngày xe chở một chuyến gồm các kiện liên tiếp tiếp theo trong hàng, tổng không quá tải trọng xe. Phải chở xong trong D ngày. Dòng đầu có n, D (1 ≤ D ≤ n ≤ 10⁵), dòng thứ hai có n số w_i (1 ≤ w_i ≤ 10⁹). In ra tải trọng xe nhỏ nhất.

Ví dụ:

Nhập	In ra
10 5 1 2 3 4 5 6 7 8 9 10	15

Kiểm tra: nhập

8 3
30 12 45 7 60 21 9 50

Xem đáp số

87

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Chuồng bò

Có n chuồng trên một hàng thẳng, chuồng thứ i ở tọa độ x_i (chưa sắp xếp, khác nhau). Cần nhốt c con bò vào c chuồng khác nhau sao cho khoảng cách nhỏ nhất giữa hai con bò bất kỳ lớn nhất có thể. Dòng đầu có n, c (2 ≤ c ≤ n ≤ 10⁵), dòng thứ hai có n số x_i (0 ≤ x_i ≤ 10⁹). In ra khoảng cách đó.

Ví dụ:

Nhập	In ra
5 3 1 2 8 4 9	3

Kiểm tra: nhập

8 4
0 100 3 47 52 99 20 75

Xem đáp số

25

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Bó hoa

Có n bông hoa trồng thành hàng, bông thứ i nở vào ngày b_i (từ ngày đó trở đi luôn nở). Cần làm m bó, mỗi bó gồm k bông liền nhau đã nở, mỗi bông chỉ dùng cho một bó. Dòng đầu có n, m, k (1 ≤ n ≤ 10⁵, 1 ≤ m, k ≤ 10⁵), dòng thứ hai có n số b_i (1 ≤ b_i ≤ 10⁹). In ra ngày sớm nhất làm đủ m bó, hoặc -1 nếu không bao giờ làm đủ.

Ví dụ:

Nhập	In ra
7 2 3 7 7 7 7 12 7 7	12

Kiểm tra: nhập

10 3 2
5 1 9 3 3 8 2 10 4 6

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Xây thêm trạm xăng

Trên đường cao tốc có n trạm xăng ở các km x₁ nhỏ hơn x₂ nhỏ hơn … nhỏ hơn x_n. Được xây thêm nhiều nhất k trạm ở các km nguyên bất kỳ. Dòng đầu có n, k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10⁹), dòng thứ hai có n số x_i tăng ngặt (0 ≤ x_i ≤ 10⁹). In ra khoảng cách lớn nhất giữa hai trạm kề nhau nhỏ nhất có thể đạt được (một số nguyên).

Ví dụ:

Nhập	In ra
3 2 0 10 30	10

Kiểm tra: nhập

6 5
0 7 100 135 140 1000

Xem đáp số

144

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Đèn đường

Con đường là đoạn từ 0 đến L. Có n ngọn đèn ở các vị trí x_i, mỗi đèn chiếu sáng mọi điểm cách nó không quá r. Dòng đầu có n, L (1 ≤ n ≤ 10⁵, 1 ≤ L ≤ 10⁹), dòng thứ hai có n số x_i (0 ≤ x_i ≤ L, chưa sắp xếp, có thể trùng). In ra số nguyên r nhỏ nhất để mọi điểm của con đường (kể cả điểm không nguyên) đều được chiếu sáng.

Ví dụ:

Nhập	In ra
3 10 2 9 5	2

Kiểm tra: nhập

6 1000
120 990 400 401 700 15

Xem đáp số

150

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Nâng điểm thấp nhất

Lớp có n bạn, bạn thứ i được a_i điểm. Thầy có k lượt cộng điểm, mỗi lượt cộng 1 điểm cho một bạn tùy chọn (không cần dùng hết). Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10⁹), dòng thứ hai có n số a_i (0 ≤ a_i ≤ 10⁹). In ra điểm thấp nhất của lớp lớn nhất có thể sau khi cộng.

Ví dụ:

Nhập	In ra
4 5 3 7 1 4	4

Kiểm tra: nhập

6 100
50 20 35 80 20 60

Xem đáp số

56

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Nâng cao

Bài 17. Trung bình cộng lớn nhất

Dòng đầu có n, L (1 ≤ L ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁶). Xét mọi đoạn liên tiếp có ít nhất L phần tử. In ra phần nguyên (làm tròn xuống) của trung bình cộng lớn nhất trong các đoạn đó.

Ví dụ:

Nhập	In ra
6 3 1 12 -5 -6 50 3	15

Kiểm tra: nhập

10 4
-3 8 -1 6 -20 4 4 9 -2 5

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Trung vị lớn nhất

Trung vị của một đoạn gồm len số là số đứng ở vị trí thứ (len + 1) / 2 (làm tròn xuống) khi xếp đoạn đó tăng dần. Dòng đầu có n, k (1 ≤ k ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ n). In ra trung vị lớn nhất trong các đoạn liên tiếp có ít nhất k số.

Ví dụ:

Nhập	In ra
5 3 1 2 3 2 1	2

Kiểm tra: nhập

10 4
3 9 1 8 7 2 10 6 4 5

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Leo núi

Bản đồ là bảng h hàng, w cột, mỗi ô ghi độ cao. Từ một ô được đi sang ô chung cạnh. Một đường đi có độ khó bằng chênh lệch độ cao lớn nhất giữa hai ô liên tiếp trên đường. Dòng đầu có h, w (1 ≤ h, w ≤ 300), h dòng sau mỗi dòng có w số (0 ≤ độ cao ≤ 10⁶). In ra độ khó nhỏ nhất của đường đi từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Ví dụ:

Nhập	In ra
3 3 1 2 2 3 8 2 5 3 5	2

Kiểm tra: nhập

4 5
10 12 30 31 40
50 15 16 70 41
9 80 18 19 45
90 91 99 21 20

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Giải phương trình bằng tìm kiếm nhị phân

Nhập số nguyên c (0 ≤ c ≤ 10⁹). In ra nghiệm thực x của phương trình x³ + x = c, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 10 thì in ra 2.000000.

Kiểm tra: nhập 123456789.

Xem đáp số

497.933190

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.