引例：一串连续的 000 和一串连续的 111 怎么找到第一个 111 ？ 例如 0 0 0 1 1 1 1 1 2 3 4 5 6 7 显然可以用二分 以上面的例子举例 一开始 l=1,r=7,mid=4l=1,r=7 ,mid=4l=1,r=7,mid=4 .然而 a[mid]=1a[mid] = 1a[mid]=1 。所以要移动右端点， r=midr=midr=mid ，那么 rrr 能等于 mid−1mid-1mid−1 吗？ 显然是不能的，如果 midmidmid 恰好是答案就错了！ 接着 l=1,r=4,mid=2l=1,r=4 ,mid = 2l=1,r=4,mid=2 然后 a[mid]=0a[mid]=0a[mid]=0。所以要移动左端点 , l=mid+1l=mid+1l=mid+1,因为 a[mid]=0a[mid]=0a[mid]=0,所以mid 不可能是第一个 111 ，所以 l=mid+1l=mid+1l=mid+1; 接着 l=3,r=4,mid=3l=3,r=4 ,mid=3l=3,r=4,mid=3,然后 a[mid]=0a[mid]=0a[mid]=0。同上 最后 l=4,r=4,mid=4l=4,r=4 ,mid=4l=4,r=4,mid=4 然后停止。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思考一个问题这种做法的二分什么时候会停止？ 显然是 l>=rl>=rl>=r 的时候，所以当 l=4,r=4l=4,r=4l=4,r=4 的时候循环就停止了。 那么最后的答案是什么呢？也就是第一个 111 的位置应该在哪呢？就存放在最后的左端点里 在当前这个样例里恰好第一个 111 就是 在 lll 这个位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 用同样的做法来看下一道二分答案的题 链接描述 同样的把问题抽象成 0000111 这样的问题 0 0 0 1 1 1 1 1 2 3 4 5 6 7 那么现在 000 表示什么呢？表示当前的高度能够砍出 MMM 长度的木材 那么 111 表示什么呢？ 表示当前的高度不能砍出 MMM 长度的木材 sososo 如果按照这样的表示方法，最后的答案应该是什么呢？ 是 LLL 吗 LLL 表示的是第一个 111 ，但在这个题里要求是最后一个 000 那么最后一个 000 就是 L−1L-1L−1 对于这类题目，跟前面题目不同的就是 check 函数里不同，二分的模板是一样的 一般二分的题目只会输出第一 111 或者是输出最后一个 000

二分答案的模版

#include<bits/stdc++.h> using namespace std; int main(){ int n,m,a[1000005]; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int mx=a[1]; for(int i=2;i<=n;i++){ if(a[i]>mx){ mx=a[i]; } } int l=0,r=mx,mid,s,ans; while(l<=r){ mid=(l+r)/2; s=0; for(int i=1;i<=n;i++){ if(a[i]>mid){ s+=a[i]-mid; } } if(s>=m){ l=mid+1; ans=mid; }else{ r=mid-1; } } cout<<ans; return 0; }

我们发现，HHH 在答案区间 [1,max⁡(ai)][1,\max(a_i)][1,max(ai )] 内得到的木材长度非严格单调递减。确定了答案的单调性，我们可以使用二分答案。时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。

暴力枚举： #include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<map> using namespace std; int main() { long long int n,m; long long a[1000005]; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } int max=1; for(int i=1;i<=n;i++) { if(a[i]>max)max=a[i]; } for(int j=max;j>=1;j--) { int sum=0; for(int i=1;i<=n;i++) { if(a[i]>j)sum+=a[i]-j; } if(sum>=m) { cout<<j; break; } } return 0; }

首先要明确这道题是用二分的 ( 因为有标签 )： 有单调性 提高伐木机的高度，显然地，得到的木头会减少。 同样地，放低得到的木头会增多。 而正因为答案有单调性，所以我们可以使用二分。 数据范围大 显然，1e6 的 n 和 1e9 的数据量对于暴力枚举是不太友好的 穷举的话，复杂度大概是 O(n⋅m)O(n·m)O(n⋅m) 绝对应该会超 然鹅二分就不会了，二分答案只要 O(n⋅logm)O(n·log m)O(n⋅logm) 应该是不会超的qwq

#include<bits/stdc++.h> using namespace std; int main(){ int n,m,a[1000005]; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int mx=a[1]; for(int i=2;i<=n;i++){ if(a[i]>mx){ mx=a[i]; } } int l=0,r=mx,mid,s,ans; while(l<=r){ mid=(l+r)/2; s=0; for(int i=1;i<=n;i++){ if(a[i]>mid){ s+=a[i]-mid; } } if(s>=m){ l=mid+1; ans=mid; }else{ r=mid-1; } } cout<<ans; return 0; }

#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N]; long long n,m; bool check(int x){ long long sum=0; for(int i=1;i<=n;i++){ if(a[i]>x) sum+=a[i]-x; } return sum>=m; } int main(){ }

#include <bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N]; int main(){ /*1,答案区间[l,r]->[0,hight(树的最大值)] 2,ans(代表锯子在mid时，锯下的总和) 如果(ans>=m),记录mid,[l,r]->[mid+1,r] 否则，不记录mid，[l,r]->[l,mid-1] */ int n,m,num=0; cin>>n>>m; int l=0,r=0;//答案区间 for (int i=1;i<=n;i++) { cin>>a[i]; r=max(r,a[i]); } //二分 while(l<=r){ int mid=(l+r)/2; int ans=0;//ans(代表锯子在mid时，锯下的总和) for (int i=1;i<=n;i++){ if(a[i]>mid) ans+=a[i]-mid; } if (ans>=m){//如果(ans>=m),记录mid,[l,r]->[mid+1,r] l=mid+1; num=mid; }else{//否则，不记录mid，[l,r]->[l,mid-1] r=mid-1; } } cout<<num; return 0; }