AcWing 1227. 分巧克力（二分）

AcWing 1227. 分巧克力

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
struct chocolate{
	int l;
	int w;
	int minlen;
	bool operator <(const struct chocolate& c)
	{
		return minlen<c.minlen;
	 } 
}ch[N];
int n,k;
bool check(int sup)
{
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		cnt += (ch[i].l/sup)*(ch[i].w/sup);
		if(cnt>=k)return true;
	}
	return false;
}
int main()
{
	
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>ch[i].l>>ch[i].w;
		ch[i].minlen=min(ch[i].l,ch[i].w);
	}
	//sort(ch,ch+n);没sort也可以过
	int l=0,r=1e5,res;
	while(l<=r)
	{
		int mid = l + (r-l)/2;
		if(check(mid))
		{
			l=mid+1;
			res=mid;
		}
		else
			r=mid-1;
	}
	cout<<res;
	return 0;
}