二分问题
程序员文章站
2022-06-02 21:24:46
...
Powered by:AB_IN 局外人
求最小段的最大值,求最大段的最小值,很明显是要用二分思想。
P1182 数列分段 Section II
求一个正整数,即每段和最大值最小为多少。
这里二分思想是什么意思呢?我感觉是这样的。
- 首先是范围,如果要确定这个数是多少,还有用二分,那么必须知道它的
l
l
l和
r
r
r是多少,这样才能不断二分。
最小值肯定是数组里的最大值,因为每段和无论如何都会有一个包含一个最大值。
最大值就是数组的和。 - 其次,在求的时候就必须想象此时的
m
i
d
mid
mid就是结果,就是每段和最大值的最小,然后通过
c
h
e
c
k
check
check函数不断检验。这里我们用前缀和记录数组,所以每段和可以表示为
a[r]-a[l-1]
。 - 接下来就是介绍重点 c h e c k check check函数了: i i i从1开始遍历到 n n n,一开始 n o w now now为0,(因为公式里是 l − 1 l-1 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]
a[1]是肯定会记入基站的,因为从小到大排序了,
a
[
1
]
a[1]
a[1]最小,所以
c
n
t
cnt
cnt一开始为1,
i
i
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;
}