题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，
小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数;
- 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入描述
第一行包含两个整数 N,K (1≤N,K≤10’5)。
以下 N 行每行包含两个整数 Hi,Wi (1≤Hi,Wi≤10‘5)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
输入输出样例
示例
输入
2 10
6 5
5 6
输出
2
思路
- 首先，明确一个概念：并不是需要恰好切为k个，而是保证至少k个，并且最大
- 其次，如何确定大小。分别求出每块巧克力可以分出的最大值，然后找到最大值里的最小值。
- 如何求最大值，通过二分查找法，因为规定长和宽不超过10’5，我们从中间数开始，进行查找，每次查找都要检查是否符合条件。符合条件者寻找右边更大的数，不符合条件者寻找左边的最大数。
- 条件有两个，一：是否可以被原巧克力切。二：是否加起来能大于等于k。
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100005],w[100005];
bool check(int mid){
int sum = 0;
for(int i = 0;i < n;++i){
sum += (h[i]/mid) * (w[i]/mid);
}
if(sum >= k){
return true;
}
else{
return false;
}
}
int main(){
cin >> n >> k;
for(int i = 0;i < n;++i){
cin >> h[i] >> w[i];
}
int l = 1;
int r = 100000;
int max = 0;
while(l < r){
int mid = l + (r - l)/2 + 1;
if(check(mid)){
max = mid;
l = mid;
}
else{
r = mid - 1;
}
}
cout << max << endl;
return 0;
}
- 代码中有一个细节，mid在取值的时候要+1，原因是，我们使用二分查找法选择的是最大数。使用l < r 作为循环条件，将数缩小到两个数的范围时进行判断，如果左侧为合适的值，l不动，r也不动，就会一直陷入死循环，而循环条件是为了当两数两数相等时退出循环，两数任意一个数都可以拿出来进行操作。所以为了避免死循环，就要保证每次选择右边的数。
- 具体理解可以查看我的博客二分查找法学习心得（如何具体问题具体分析） - ku然 - 博客园 (cnblogs.com)