二分
参考y总二分模板 https://www.acwing.com/blog/content/31/
时间复杂度 $O(nlogn)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int ch = 100010;
int h[ch], w[ch];
int n,k;
bool check(int a){ //判断分好后的巧克力个数是否>=k
int num = 0;
for(int i=0; i<n; i++) num += h[i]/a*(w[i]/a);
if(num>=k) return true;
else return false;
}
int l = 1, r = 1e5; //边长所有可能情况
int main(){
int mid;
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++) scanf("%d%d", &h[i], &w[i]);
while(l<r){
mid = l + r + 1 >> 1; //上取整
if(check(mid)) l = mid; //在[mid,r]区间里继续找边长最大值
else r = mid-1;
}
printf("%d\n", l);
return 0;
}