AcWing
1227. 分巧克力
二分枚举分出的正方形的边长，对每个边长，判断是否能分出足够多的块数，搜索出恰好大于等于目标块数的分法(正方形边长)。check函数是，对每块巧克力，假设其边长分别为h[i]、w[i]，其能按边长a分出的正方形数就是$block_i = \lfloor \frac{h[i]}{a} \rfloor \cdot \lfloor \frac{w[i]}{a} \rfloor$，将所有巧克力分出的block相加，与目标块数k比较。
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 1e5 + 10;
int h[N], w[N];
typedef long long LL;
LL getblocks(int a){
LL blocks = 0;
for(int i = 1; i <= n; i++){
int aa = h[i] / a;
int bb = w[i] / a;
blocks += (LL)aa * bb;
}
return blocks;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
int maxe = -1;
for(int i = 1; i <= n; i++){
cin >> h[i] >> w[i];
if(h[i] > maxe) maxe = h[i];
if(w[i] > maxe) maxe = w[i];
}
int l = 1, r = maxe;
while(l < r){
int mid = l + r + 1 >> 1;
if(getblocks(mid) >= k) l = mid;
else r = mid - 1;
}
cout << r;
return 0;
}