Nguồn: Cuộc thi Lanqiao Cup C++ A/B Nhóm 8

Nhãn thuật toán: Tìm kiếm nhị phân

Mô tả bài toán

Vào Ngày Thiếu nhi, có K bạn nhỏ đến nhà bạn Minh chơi.

Bạn Minh đã chuẩn bị những thanh sô-cô-la quý giá để đãi các bạn nhỏ.

Bạn Minh có tổng cộng N thanh sô-cô-la, trong đó thanh thứ i có kích thước Hi × Wi.

Để đảm bảo sự công bằng, bạn Minh cần cắt K thanh sô-cô-la từ N thanh này để phân phát cho các bạn nhỏ.

Các thanh sô-cô-la cắt ra phải đáp ứng:

• Có dạng hình vuông với cạnh là số nguyên
• Kích thước bằng nhau
• Ví dụ: một thanh sô-cô-la 6×5 có thể cắt thành 6 thanh 2×2 hoặc 2 thanh 3×3.

Chắc chắn các bạn nhỏ đều muốn nhận được những thanh sô-cô-la càng lớn càng tốt. Bạn có thể giúp Minh tính toán kích thước cạnh lớn nhất có thể được không?

Định dạng đầu vào

Dòng đầu tiên chứa hai số nguyên N và K.

Dưới đây là N dòng, mỗi dòng chứa hai số nguyên Hi và Wi.

Đầu vào đảm bảo mỗi bạn nhỏ ít nhất nhận được một thanh sô-cô-la 1×1.

Định dạng đầu ra

Xuất kích thước cạnh lớn nhất có thể của các thanh sô-cô-la vuông.

Phạm vi dữ liệu

1≤N,K≤10^5,
1≤Hi,Wi≤10^5

Ví dụ đầu vào:

2 10
6 5
5 6

Ví dụ đầu ra:

2

Phương pháp giải

Mục tiêu của chúng ta là tìm kích thước cạnh lớn nhất có thể để cắt ra K thanh sô-cô-la vuông có kích thước bằng nhau. Các bạn nhỏ đều muốn nhận được những thanh sô-cô-la càng lớn càng tốt.

Chúng ta cần tìm mối quan hệ giữa "số lượng" và "kích thước cạnh". Với điều kiện các miếng sô-cô-la phải là hình vuông có cạnh nguyên, chúng ta có thể tính số lượng miếng có thể cắt từ một thanh sô-cô-la bằng công thức: num += (chiều cao / cạnh) × (chiều rộng / cạnh).

Quan sát thấy rằng khi kích thước cạnh tăng lên, số lượng miếng sô-cô-la giảm xuống. Trong phạm vi có tồn tại một giá trị cạnh mid sao cho tổng số miếng cắt ra từ tất cả các thanh sô-cô-la bằng K, và đây chính là giá trị cạnh lớn nhất chúng ta cần tìm.

Chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân để tìm giá trị mid này. Nếu với một giá trị mid nào đó, số lượng miếng sô-cô-la cắt ra được lớn hơn hoặc bằng K, chúng ta sẽ thử tăng mid lên (tìm kiếm bên phải). Khi không thể tăng mid nữa, giá trị mid hiện tại chính là kết quả cần tìm.

Mã nguồn C++ - Tìm kiếm nhị phân O(n log n)

#include <iostream>
using namespace std;

const int MAX_SIZE = 100010;
int chieucao[MAX_SIZE], chieurong[MAX_SIZE], so_thanh, so_ban;

bool kiem_tra(int canh)
{
    int tong_so_mieng = 0;
    for (int i = 0; i < so_thanh; i++)
    {
        tong_so_mieng += (chieucao[i] / canh) * (chieurong[i] / canh);
        if (tong_so_mieng >= so_ban) return true;
    }
    return false;
}

int main()
{
    cin >> so_thanh >> so_ban;
    for (int i = 0; i < so_thanh; i++) 
        cin >> chieucao[i] >> chieurong[i];
    
    int trai = 0, phai = 100000;
    while (trai < phai)
    {
        int giua = trai + phai + 1 >> 1;
        if (kiem_tra(giua)) trai = giua;
        else phai = giua - 1;
    }
    cout << trai;
    return 0;
}