二分查找
…
题目种巧克力为标准矩形,要求分成形状是正方形,边长是整数,大小相同。则能猜
到:在一块巧克力中,想可能尽多地切出小正方形,则分成地小正方形应该是临近的,也
就是可以从角落处开始顺序分成。
由于在c语言中/是下取整,我们也刚好可以求出一块巧克力分成所需正方形的个数,
令所需正方形边长为x,则个数为(长/x)*(宽/x),最后使所有巧克力分出的正方形个数大等
于K人数。
则最后问题转到找到符合要求的正方形的最大值,我们可以使用二分查找来求。
二分查找中,正方形的边长最小是1,则满足要求的左边界已经确定,则我们最终要找
最大值,也就是满足要求的右边界,则模板就是
while(l<r)
{
int mid=l+r+1>>1;
if(check(i)) l=mid; check(i)为判断满足某个性质
else r=mid-1;
}
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N]; //定义数组a,b存储长,宽
int n,k;
bool check(int m) //实现要求
{
int sum=0;
for(int i=0;i<n;i++)
{
sum+=(a[i]/m)*(b[i]/m);
if(sum>=k) return true;
}
return false;
}
int main()
{
cin >> n >> k;
for(int i=0;i<n;i++) cin >> a[i] >> b[i];
int l=0,r=1e5+10;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << r << endl;
return 0;
}