题目描述
有N块巧克力,K个小朋友,第i块巧克力是由Hi*Wi个方格组成的,要使每个小朋友分到的巧克力一样大,且都是正方形,问如何切,可以使小朋友们得到的巧克力最大,即使切得的每一块巧克力边长最长.
算法
(整数二分) $O(logn)$
参考模板
https://www.acwing.com/blog/content/31/
思路
这道题正常想很难找到突破口,如果我们能够利用逆向思维,把它转化为一个判定问题(类似昨天y总讲的剪绳子问题),那么就会变得容易.试想,如果把N块巧克力都切成边长为mid的正方形,可以切多少块?够不够这几个小朋友分呢?如果不够怎么办?如果,切的块数多了怎么办?
这时,我们就想到用二分的方法,逐步逼近我们要找的答案.
如果不够,说明我们每一块切的太大了,这时就要减小每块的边长,使其小于mid,即在二分区间的左边找答案.反之,则要在二分区间的右边找答案(>mid)
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n,k; //n代表巧克力数,k代表小朋友数
int h[N],w[N]; //分别存储长宽两条边的长度
//判断切得的总块数是否大于人数
bool check(int mid)
{
int cnt = 0; //cnt用来计切得的总块数
for(int i = 0; i < n ; i ++ )
cnt += (h[i]/mid) * (w[i]/mid);
//如果在h[i]边上切可以切几块?如果在w[i]边上切呢?相乘就是总块数.
return cnt >= k;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++ )
cin >> h[i] >> w[i];
int l = 0,r = 1e5;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid)) l = mid; //满足上面说的判定条件
else r = mid - 1;
}
cout << r;
return 0;
}