一道很简单的二分,刚开始却走了很多弯路,刚开始用面积做,错了,后来一想,题目要求切一块一块的巧克力,他们是不能融合的,显然面积是不行的,只能用二分来做
那么为什么可以用二分做呢?
s=(h[i]/mid)*(w[i]/mid) i从1到n的总和
题目要求满足s>=k的mid最大值,mid有区间(1,1e5),刚开始我还以为mid的范围是(min(h,w),max(h,w)),后来被数据卡了,有些很小的巧克力其实不必再去考虑
在l,r的区间上,每次二分出来一个mid,然后check一下当前mid是否符合s>=k,符合:mid还可以再大点,s随mid增大变小,区间变为(mid,r),不符合:mid太大了,mid应该小一点使s变大,区间变为
(l,mid-1)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL h[N],w[N];
LL n,k;
bool check(int x)
{
LL s=0;
for(int i=0;i<n;i++)
{
s+=(w[i]/x)*(h[i]/x);
if(s>=k) return true;
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>h[i];
cin>>w[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<<endl;
return 0;
}
----------
```