题目描述
blablabla
样例
blablabla
算法1
(二分) $O(nlogn)$
blablabla
时间复杂度
参考文献
已知数据范围,巧克力可以是最大边长1e5的正方形,这种情况下,
可以切成1x1的1e5个巧克力 或者 1e5x1e5的1个巧克力,
有n个巧克力,k个同学,要存在一个值a可以使得每个人都能得到尽可能大的巧克力
a的值范围一定是在[1,100000]的;我们只需要尽可能快的找到
同时a还需要符合 每一块(长,宽)h,w巧克力全都能切出来:
(h/a)*(w/a):可以计算 边长为a的正方形可切出块数
用上式计算出每一块都能被切出来且最后切出的总数大于等于k(可以分给k个同学)
总之,找出1-100000里面的a,并且确保a是可以让巧克力切出满足条件的形状和块数
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,k;
int h[N],w[N];
//检查边长为a的正方形是否可以切出来
bool fun(int a){
int num = 0;
for(int i = 0; i < n; i++){
num += (h[i]/a)*(w[i]/a);
if(num >= k) return true;
}
return false;
}
int main(){
cin >> n >>k;
for(int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;
while(l <= r){
int mid = (l+r)/2;
if(fun(mid)){
//判断条件改为,如果符合要求,左边坐标往前走,找更大的
l = mid+1;
}
else{
//不符合要求,说明找大了,可以把右边往后,找更小的
r = mid-1;
}
}
cout << r;
return 0;
}
对于1-100000找一个数,用二分法常用的两个:(taeget为目标值)
[l,r]:在左闭右闭区间
while(l <= r){
int mid = (l+r)/2;
if(mid < target){
l = mid+1;
}
else if(mid > target){
//while循环已经排除了r端点,所以下一次不需要更新成mid
r = mid-1;
}
}
[l,r):在左闭右开区间
while(l < r){
int mid = (l+r)/2;
if(mid < target){
l = mid+1;
}
else if(mid > target){
//while循环没有排除右边的r端点,所以下一次需要包括mid
r = mid;
}
}