P8647 [蓝桥杯 2017 省 AB] 分巧克力--2024蓝桥杯冲刺省一

本文主要是介绍P8647 [蓝桥杯 2017 省 AB] 分巧克力--2024蓝桥杯冲刺省一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

知识点讲解：二分算法--模板及原理总结

思路：读完题发现答案的边长是具有二段性，单调性的。就是假如答案为ans，那么所有

<=ans的值为【1，ans】都满足题意，那么我们就是寻找满足这个性质的最大值。
 

ans的范围是1~1e5，【1~ans】都是满足的结果，（ans，1e5】都是不满足的结果

所以我们用第一套模板：mid=（l+r+1) / 2， l=mid，r=mid-1；最后写check函数。

（反之，我们就用第二套模板，mid=（l+r）/ 2；，r=mid，l=mid+1；

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'
#define LL __int128using namespace std;const int N=2e5+10,M=1e3+10,mod=998244353,INF=0x3f3f3f3f;int n,k;
int h[N],w[N],c[N],pre[N];
bool check(int mid)
{int cnt=0;for(int i=1;i<=n;i++)cnt+=(h[i]/mid)*(w[i]/mid);return cnt>=k;
}signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n>>k;for(int i=1;i<=n;i++)cin>>h[i]>>w[i];int l=1,r=1e5+10;while (l<r){int  mid=(l+r+1)/2;if(check(mid))l=mid;else r=mid-1;}cout<<l<<endl;return 0;
}

这篇关于P8647 [蓝桥杯 2017 省 AB] 分巧克力--2024蓝桥杯冲刺省一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---