关于二分我的一些疑惑
查看原帖
关于二分我的一些疑惑
1229738
CyansQwQ楼主2024/5/12 08:55

刚开始,我设的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,是这样吗? 求助佬们解答

2024/5/12 08:55
加载中...