AcWing 1227. 分巧克力
原题链接
简单
作者:
硬拉tom
,
2021-01-18 11:47:17
,
所有人可见
,
阅读 297
算法
二分
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n,k,h,w;
PII ps[N];
bool check(int mid){//检测分割以mid为边长的正方形能否切出k块
int cnt=0;
for(int i=0;i<n;i++){
cnt+=(ps[i].first/mid) * (ps[i].second/mid);
}
return cnt >= k;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d%d",&ps[i].first,&ps[i].second);
}
int l=1,r=1e5,mid;
while(l<r){
mid=((l+r)>>1)+1; //二分右边界模板
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d",l);
return 0;
}