题目描述
儿童节那天有 K位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N块巧克力,其中第i块是 Hi×Wi的方格组成的长方形。
为了公平起见,小明需要从这N块巧克力中切出K块巧克力分给小朋友们。
切出的巧克力需要满足:
1.形状是正方形,边长是整数
2.大小相同
例如:一块 6×5的巧克力可以切出6块2×2的巧克力或者2块3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?
样例
输入:
2 10
6 5
5 6
输出:
2
二分
C++ 代码
核心代码是抄的其他题解的大佬的模板,比如将大巧克力如何分为不同规模的小巧克力那里,本人基础比较差,很多地方都想不到,但是通过看了几个大佬的题解,以及评论区各位大佬的解读,大概是理解了一些,有问题可以一起交流,第一次发题解,其实应该算是偷的别人的代码,哈哈,大家可以一起交流
#include <bits/stdc++.h>
using namespace std;
const int K = 1e+5;
const int H = 1e+5,W = 1e+5;
int n,k;
int h[H],w[W];
int judge(int x){
int res = 0;
for(int i = 0 ; i < n ; i++) res += (h[i]/x) * (w[i]/x); //抄的大佬的模板,计算所有巧克力可以分为res个x * x规模的小巧克力
return res;
// if(res >= k) return true;
// else return false;
}
int main(){
int l = 0 , r = W;
scanf("%d %d\n",&n,&k);
for(int i = 0 ; i < n ; i++) scanf("%d %d\n",&h[i],&w[i]);
for(int j = 0 ; j < n ; j++) r = max({r,h[j],w[j]}); //缩小需要查找的范围,不过大佬说其实这个影响不大
while(l < r){
int mid = l + r + 1 >> 1; //由于是计算二段性的右端点,此时的l=mid,所以计算mid时要加1
if(judge(mid) >= k) l = mid; //判断mid * mid规模的小巧克力数量是否满足小朋友的数量
else r = mid-1;
}
cout << l <<endl;
return 0;
}