每日一题 二分查找分巧克力
先复习一下二分查找基本格式
check函数{
}
l=0;
r=10000;
while(l+1!=r){
if(check()条件){
l = mid;
else //这要看题目条件往哪里缩小范围
r = mid-1;
}
}看下这道题
先找一下条件设置check函数，读题可以发现条件就是每个孩子都要分到一块巧克力，因为巧克力是正方形的，所以总数就是长和宽能获取的值相乘。分析到这已经差不多了，看看代码
#include <bits/stdc++.h>
using namespace std;
const int def=100005;
int h[def]={0};
int w[def]={0};
int n,k;
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 Max = 0;
int l=1;
int r=100000;
while(l <=r){
int mid = (l+r)/2;
if(check(mid)){
Max = mid;
l = mid+1;
}
else r=mid-1;
}
cout<<Max;
return 0;
}
这道题我一开始想麻烦了，我以为要分类看它切后剩下的边能不能再组成巧克力。但是sum就是每边的数量相乘。