【蓝桥杯】分巧克力--二分查找

解题思路:

注意事项:

参考代码:

//分巧克力问题--标准的二分模板题
//判断条件以及二分上下界 
#include <bits/stdc++.h>
using namespace std;
const int vinf = 1e6+100;
int hei[vinf];  //存储长 
int wid[vinf];  //存储宽 
int n,k;
int ans = 0;
//判断当前正方形的边长是否满足条件
bool isok(int ss)
{
	int temp = 0;
	for(int i=1;i<=n;++i){
		temp += (hei[i]/ss)*(wid[i]/ss);
	}
	if(temp>=k)
		return true;
	return false;
} 
int main(){
	//输入数据 
	cin>>n>>k; 
	for(int i=1;i<=n;++i){
		cin>>hei[i]>>wid[i];   //第 i 块巧克力的尺寸 
	}
	//开始二分处理
	int left = 1;   //最小也是为1
	//最大的正方形的边长是 长度最da的巧克力的chang
	int vmax = 0;
	for(int i=1;i<=n;++i){
		vmax = max(vmax,wid[i]);
		vmax = max(vmax,hei[i]);
	}
	while(left<=vmax)
	{
		int mid = left + (vmax - left)/2;
		if(isok(mid)){
			ans = mid;
			left = mid + 1;
		}
		else
			vmax = mid - 1;
	}
	cout<<ans<<'\n';
	return 0;
}