二分问题

Powered by:AB_IN 局外人

求最小段的最大值，求最大段的最小值，很明显是要用二分思想。

P1182 数列分段 Section II

求一个正整数，即每段和最大值最小为多少。 这里二分思想是什么意思呢？我感觉是这样的。

首先是范围，如果要确定这个数是多少，还有用二分，那么必须知道它的$l$和$r$是多少，这样才能不断二分。 最小值肯定是数组里的最大值，因为每段和无论如何都会有一个包含一个最大值。 最大值就是数组的和。其次，在求的时候就必须想象此时的$mid$就是结果，就是每段和最大值的最小，然后通过$check$函数不断检验。这里我们用前缀和记录数组，所以每段和可以表示为a[r]-a[l-1]。接下来就是介绍重点$check$函数了：$i$从1开始遍历到$n$，一开始$now$为0，（因为公式里是$l-1$），接下来看代码注释即可。 #include<bits/stdc++.h> typedef long long ll; using namespace std; ll n,m,l,r; ll a[1000001],sum[1000001]; inline bool check(ll mid){ int now=0; int cnt=0;//计数器 for(int i=1;i<=n;i++){ if(sum[i]-sum[now]>mid){//如果i到now的这一段和>mid了，那么计数器+1，重新往右取区间 cnt++; now=i-1; } } return cnt>=m; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=a[i]+sum[i-1]; l=max(l,a[i]);//最小值为整个数组最大的数（因为求的是每段最大和的最小） } r=sum[n];//右边界是前缀和的最大值（即数组的和） while(l<=r){ ll mid=(l+r)>>1; if(check(mid)) l=mid+1;//如果合法说明比mid大的数都合法，左边界右移。 else r=mid-1;//如果不合法说明比mid大的数都不合法，右边界左移。 } cout<<l; return 0; }

Base Station Sites

同样的，这里是放基站问题，就是bool函数不太一样，这里$a[1]$是肯定会记入基站的，因为从小到大排序了,$a[1]$最小，所以$cnt$一开始为1，$i$从2开始遍历。

#include <bits/stdc++.h> using namespace std; const int N=1e6+10; int n, m, a[N],l,r; bool check(int mid) { int cnt=1,now=1; for(int i=2;i<=n;i++){ if(a[i]-a[now]>=mid){ cnt++; now=i; } } return cnt>=m; } int main() { while (~scanf("%d%d", &n, &m) && n!=0 && m!=0) { int mx=-1; for(int i=1;i<=n;i++){ scanf("%d", &a[i]); mx=max(a[i],mx); } sort(a+1,a+1+n); l=1;r=mx; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } printf("%d\n",r); } return 0; }