蓝桥杯 分巧克力（二分）

思路：标准二分题，二分每一次选择的边长X。

check（x）：对于一块矩形巧克力能分出的边长x正方形数量为(矩形长/x)*(矩形宽/x)，如果所有的巧克力能分出>=朋友人数,则此方案可行l=x,否则不可行r=x-1。

Code:

#include<iostream>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
#include<string>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;

int n, s;
int lst[Max][2];

int check(int x)
{
   

	int sum = 0;
	for (int i = 1;i <= n;i++)
	{
   
		sum += (lst[i][0] / x) * (lst[i][1] / x);
	}
	if (sum >= s)return 1;
	else return 0;
}



int main()
{
   
	cin >> n >> s;
	for (int i = 1;i <= n;i++)cin >> lst[i][0] >> lst[i][1];
	int l = 1, r = 1e9 + 5;
	while (l<r)
	{
   
		int mid = (l + r+1) / 2;
		if (check(mid))l = mid;
		else r = mid - 1;
	}
	cout << l;
}