Day04 二分答案
2026-08-05 22:17:00
发布于：广东
7阅读
0回复
0点赞
二分答案解题思路:
确定枚举思路，通过二分答案对枚举思路进行优化
1.确定枚举对象:一般求什么就枚举什么;
2.确定枚举范围:枚举边界，可能的最小值和最大值;
3.确定 check 函数写法!
通常根据限定内容来写check;
check 需要先手动模拟，然后用代码实现模拟过程
4.判断答案是否满足单调性:
能否通过中间位置是否可行，去掉其中一半的可能性，缩小检查范围
5.对枚举答案进行二分:
1答案 越大越好:二分答案求上界;
2答案 越小越好:二分答案求下界
砍树(求上界)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
long long n,m;
int a[N];
bool check(long long h) {
long long sum=0;//获得的木柴
for(int i=1;i<=n;i++){
if(a[i]>h)sum += a[i]-h;
}
return sum >= m;//m是想要获得的总数
}
int upper_answer(int l, int r){
int ans=0;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
ans = mid;
l = mid+1;//砍多了，锯片向上，往右边
}else r=mid-1; //砍少了，锯片向下，往左边
}
return ans;
}
int main(){
cin>>n>>m;
int maxnn=0;
for(int i=1;i<=n;i++){
cin>>a[i];
maxnn=max(maxnn,a[i]);
}
int l=0,r=maxnn;
//二分最高的树到0 为锯片高度 二分答案
cout << upper_answer(l,r);
return 0;
}
吃香蕉(求下界)
#include <bits/stdc++.h>
using namespace std;
int n,h;
int a[2000005];
bool check(int x)
{
long long cnt=0;
for(int i=1;i<=n;i++)
{
cnt+=(a[i]+x-1)/x;
}
return cnt<=h;
}
int lower_answer(int l,int r)
{
long long ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
int main()
{
cin>>n>>h;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int l=1,r=1e9;
cout<<lower_answer(l,r);
return 0;
}
这里空空如也
有帮助，赞一个