分析
经典二分问题,可以和昨天的剪绳子做对比。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,k,a[N],b[N];
bool check(int mid)
{
int ans=0;
for(int i=0;i<n;i++)
{
ans+=floor(a[i]/mid)*floor(b[i]/mid);
if(ans>=k) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
int l=1,r=1e5;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
代码水到渠成