AcWing 1227. 分巧克力
原题链接
简单
作者:
wyf
,
2021-01-15 10:36:14
,
所有人可见
,
阅读 376
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
PII a[N];
int n,m;
bool check(int x){
int res=0;
for(int i=0;i<n;i++){
res+=(a[i].first/x)*(a[i].second/x);//看每一块可以贡献多少
if(res>=m)return true;
}
return false;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
a[i]={x,y};
}
int l=1,r=1e5;//二分
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r<<endl;
return 0;
}