Original Link

思想：

• 二分。
• 巧克力的边长最大为 1e5。
• 考虑二分：
  • 若当的边长满足要求，则说明还有可能取更长的边长；
  • 若当前边长不满足要求，则说明当前边长不可能是最终答案；
  • 当二分边界相交时即可得到最大的边长。
• 利用 pair<int, int> a[N] 存储边长数据，第 a[i] 块巧克力可分割的数量为 (a[i].first / t) * (a[i].second / t)。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;

const int N = 1e6 + 3;

pair<int, int> a[N];

bool check(int t){  //判断是否满足条件
    int cnt = 0;
    for(int i = 0; i < n; i ++){
        cnt += (a[i].first / t) * (a[i].second / t);
        if(cnt >= m) return 1;  //当前分割数量已经满足，提前返回 true
    }
    return 0;
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> a[i].first >> a[i].second;

    int l = 1, r = 1e5;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;  //二分终点即为答案
}

int main(){
    solve();
    return 0;
}