【蓝桥杯】二分法求解--分巧克力

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
typedef long long ll;
const int vinf = 100010;
ll ww[100010];
ll hh[100010];
ll n,k,ans;
bool isok(ll ss)
{
    int temp = 0;
	for(int i=1;i<=n;++i){
		temp += (ww[i]/ss)*(hh[i]/ss);
	}
	if(temp>=k)
		return true;
	return false;
}
int main()
{
    cin>>n>>k;
    int w,h;
    for(int i=1;i<=n;++i){
        scanf("%lld %lld",&ww[i],&hh[i]);
    }
    ll zuo = 1;
    ll you = 100010;
    while(zuo<=you)
    {
        ll mid = zuo + (you - zuo)/2;
        if(isok(mid))
        {
            ans = mid;
            zuo = mid + 1;
        }
        else
        {
            you = mid - 1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}