YCKC【二分答案专题】题解

何为二分答案？能二分答案的题目，一定能靠暴力枚举答案代入检查拿到部分分。如果答案呈现单调有序的状态，那么可以二分优化
注意L,R的初始值设置，必须把答案所有的可能取值范围框进去

伐木

不难发现锯子越低，砍伐的树木就越长。我们直接二分锯子的高度，然后$O(N)$ 代入回去check即可

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int n,m;
int a[N];
bool check (int x) {LL sum = 0;for (int i = 1;i <= n;i++) sum += max (a[i]-x,0);return sum >= m;
}
int main ()  {cin >> n >> m;for (int i = 1;i <= n;i++) cin >> a[i];int l = 0,r = N;while (l < r) {int mid =( l + r +1 )/2;   //记得+1if (check (mid)) l = mid;   //如果当前点合法，那么答案可以更大，并且mid也有可能成为答案，所以l = midelse r= mid-1;   //对应过来的}cout << l << endl;return 0;
}

木材加工

直接二分答案，对于答案而言，代入回每段木头check，利用整除就能计算出某段木头能切割出多少。本题涉及到无解情况，注意判断。

#include<bits/stdc++.h>
using namespace std;
int A[100005];
int n,k;
bool check(int x){long long int sum=0;if(x==0)return true;for(int i=1;i<=n;i++){sum=sum+A[i]/x;if(sum>=k)return true;}return false;
}
int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&A[i]);}int L=0,R=1e8;while(L<R){int mid=(L+R+1)/2;if(check(mid)){L=mid;}else{R=mid-1;}}printf("%d",L);return 0;
}

跳石头

因为起点和终点也是石头，先把两端确定下来，
也就是$D[0]=0,D[N+1]=L$。考虑二分跳跃距离x，直接从左往右枚举石头，计算出相邻石头的跳跃距离并求和，如果该求和距离＜x，我们记录石头数量，因为这些石头都是需要被搬走的。如果求和距离大于等于x，那么我们需要重新计算跳跃的距离。这样子能保证我们搬走最少的石头且跳跃的间距尽可能的大。如果最后一段一直跳跃到终点，距离和还是＜x,那么需要再搬走一块石头，相当于把上一次的落脚点石头直接移除掉，这样子一步跳跃到终点，满足了“跳跃距离至少为x”

#include<bits/stdc++.h>
using namespace std;
int D[50005];
int n,L,m;
bool check(int x){int cnt=0;int len=0;//累计跳跃长度 int need=0;for(int i=1;i<=n+1;i++){int dis=D[i]-D[i-1];//石头间距len=len+dis;cnt++;if(i==n+1&&len<x){need=need+cnt;//把上一次的落脚点也搬走}if(len>=x){need=need+(cnt-1);//cnt-1是因为我们需要一个落脚点石头len=0;cnt=0;}}if(need>m)return false;return true;
}
int main(){scanf("%d%d%d",&L,&n,&m);D[0]=0;//起点 D[n+1]=L;//终点 for(int i=1;i<=n;i++){scanf("%d",&D[i]);}int l=1,r=L;while(l<r){int mid=(l+r+1)/2;if(check(mid)){l=mid;}else{r=mid-1;}}printf("%d",l);return 0;
}

数列分段 Section II

二分答案，表示某一段和的最大值x。考虑从左往右计算，依次来凑x。
不要超过x的值，如果超过了应该另起一段，段数++。最终判断生成的段数跟M的关系。如果在当前答案下，段数小于M，说明我们的二分的答案比较大，我们尝试缩小答案; 如果段数等于M，说明我们还有缩小答案的空间;如果段数大于M，说明我们二分的答案比较小，应该放大答案范围

#include<bits/stdc++.h>
using namespace std;
int n;
int A[100005];
int m;
bool check(int x){int cnt=1;int s=0;for(int i=1;i<=n;i++){if(s+A[i]<=x){s=s+A[i];}else{s=A[i];cnt++;}}if(cnt<=m)return true; else return false;
}
int main(){cin>>n>>m;int L=0,R=1e9;for(int i=1;i<=n;i++){cin>>A[i];L=max(L,A[i]);}while(L<R){int mid=(L+R)/2;if(check(mid)){//假设划分段的和最大值是mid  R=mid;}else{L=mid+1;}}cout<<R;return 0;
}

吃糖果

千万不要写Q次询问，for循环
1000ms只允许你跑1e8差不多
这个题是个非常明显的二分，问最少吃多少堆糖果就能达到至少X颗
这不就是二分吗，我们把糖果数组排序，从大到小做个前缀和，然后二分找位置就好了。从大到小吃能保证尽可能早地吃到目标

#include<bits/stdc++.h>
using namespace std;
int A[150005];
int Q[150005];
int sum[150005];
int x;
bool check(int pos){return sum[pos]>=x;
}
bool cmpx(int x,int y){return x>y;
}
int main() {int t;cin>>t;while(t--) {int n,q;cin>>n>>q;for(int i=1;i<=n;i++){cin>>A[i];}sort(A+1,A+1+n,cmpx);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+A[i];}sum[n+1]=2e9;while(q--){cin>>x;int L=1,R=n+1;while(L<R){int mid=(L+R)/2;if(check(mid))R=mid;else L=mid+1;}if(R==n+1)cout<<-1<<'\n';else cout<<R<<'\n';}}return 0;
}

制作蟹黄堡

也是经典二分答案，直接二分能做多少个汉堡，去检查
制作$mid$个汉堡行不行如何判断？检查凑出$mid$份食材能不能凑出来就行了

#include<bits/stdc++.h>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const int maxn = 110;LL need[3], cnt[3], price[3], money;
bool check(LL t){LL sum = 0;for(int i = 0; i < 3; ++i)sum += max(t*need[i]-cnt[i], 0LL) * price[i];return money >= sum;
}
int main() {string s;cin >> s >> cnt[0] >> cnt[1] >> cnt[2] >> price[0] >> price[1] >> price[2] >> money;for(int i = 0; i < s.length(); ++i){if(s[i] == 'B') ++need[0];if(s[i] == 'S') ++need[1];if(s[i] == 'C') ++need[2];}LL mmin = inf, ans = 0;for(int i = 0; i < 3; ++i){if(need[i] == 0) continue;mmin = min(mmin, cnt[i]/need[i]);}ans += mmin;for(int i = 0; i < 3; ++i)cnt[i] -= need[i]*mmin;LL l = 0, r = money+cnt[0]+cnt[1]+cnt[2];while(l < r){LL mid = (l+r+1)/2;if(check(mid)) l = mid;else r = mid-1;}cout << ans+l << endl;return 0;
}

玩电脑游戏

二分能直接玩的次数，带回去检验就行了。。。这应该不难吧
注意判断一开始无解的情况，我们最多最多直接充电玩到不能玩，这样子的通关数量还是小于N的话肯定无解。因为电力必须严格大于B才能充电玩，所以计算的时候要注意一点细节

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int k,n,a,b;//没开龙龙
bool check(int x){//直接玩x关 int cnt=x;//玩的关数 int le=k-x*a;//剩余电if(le<=0){return false;}if(le>b){	cnt=cnt+le/b;if(le%b==0)cnt--;}if(cnt>=n)return true;else return false; 
}
signed main(){int q;scanf("%lld",&q);while(q--){scanf("%lld%lld%lld%lld",&k,&n,&a,&b);	int now=k/b;if(k%b==0)now--;//整除的话说明全部电力都玩完了，b电力一次，但是我们要预留出“电力严格大于b才能玩”if(now<n){cout<<-1<<'\n';continue;}int L=0,R=n;while(L<R){int mid=(L+R+1)/2;if(check(mid))L=mid;else R=mid-1;	}	printf("%lld\n",L);}return 0;
}

子序列的长度

首先，我们不知道答案有多长，但是很明显，朴素的想法就是枚举长度代入计算，$O(N^2)$

推理一下，如果答案最优长度是$X$，很明显$大于等于X$的长度都可以凑出求和不少于$S$，但是长度一旦小于$X$就不行，所以很明显单调，可以二分。

#include<bits/stdc++.h>
using namespace std;
int n,s,a[1001001],b[1001001],l,r,mid,mi=2e9,ans;
int main(){scanf("%d%d",&n,&s);for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]+=a[i-1];for(int i=1;i<=n;i++){l=i+1,r=n,ans=2e9;while(l<=r){mid=(l+r)/2;if(a[mid]-a[i-1]>=s)ans=mid-i+1,r=mid-1;else l=mid+1;}//cout<<ans<<"\n";mi=min(mi,ans);}if(mi==2e9)cout<<0;else cout<<mi;return 0;
}