刚开始,我设的l=0,r=m+1;m是n块巧克力所有边的最小值,代码如下
// Problem: P8647 [蓝桥杯 2017 省 AB] 分巧克力
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8647
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,h[N],w[N],m=0x3f3f3f3f;
bool check(int x)
{
int res=0;
for(int i=1;i<=n;i++)res+=(h[i]/x)*(w[i]/x);
if(res>=k)return true;
else return false;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++){cin>>h[i]>>w[i];m=min(m,min(h[i],w[i]));}
int l=0,r=m+1;
while(l+1<r)
{
int mid=l+r>>1;
if(check(mid))l=mid;
else r=mid;
}
cout<<l;
}
int main()
{ ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
solve();
return 0;
}
代码没有AC,只有12分,但当我将m的值设为100000后,代码AC了,这是为什么嘞? 我在写帖子的时候忽然想到可能不是所有巧克力都要切,或许只用切其中一部分,就能找到合适的值,所以将r设置为m+1,是这样吗? 求助佬们解答