AcWing 1227. 分巧克力
原题链接
简单
作者:
zaozao
,
2021-02-07 17:33:01
,
所有人可见
,
阅读 296
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int h[100005],w[100005];//h和w分别表示边长
int n,k,m;//n表示巧克力个数,k表示小孩子个数,m表示最长边
bool check(int mid){
int num=0;
for(int i=0;i<n;i++){
num+=(h[i]/mid)*(w[i]/mid);
}
return num>=k;
}
int main(){
cin>>n>>k;
m=0;//用m表示最大的边
for(int i=0;i<n;i++){
cin>>h[i]>>w[i];
if(h[i]>=m) m=h[i];
else if(w[i]>=m) m=w[i];
}
int left=1,right=m,mid;
while(left<right){
mid=(left+right)/2;
if(check(mid)) left=mid+1;
else right=mid;
}
if(check(left)) cout<<left;
else cout<<left-1;
return 0;
}