二分算法适用于解的最优解具有单调性的题（如『较大的最小』或『较小的最大』或『合法条件与不合法条件』呈两侧分布之类）
1.数列分段
【题目描述】
对于给定的一个长度为N的正整数数列A，现在将其分成M段，并要求每段连续，且每段和的最大值最小。
【输入格式】
第一行包含两个正整数N，M。
第二行包含N个空格隔开的非负整数Ai。
【输出格式】
一个正整数，即每段和最大值最小为多少。
【样例】
输入：
5 3
4 2 4 5 1
输出：
6
【思路】
选定一个最大值，使每一段和不大于这个值，若能分成不大于M段，则减小最大值，直到不符合要求为止。
【代码】
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],max_a,sum_a;
bool check(int lim){
int cnt=1,sum=0;
for(int i=1;i<=n;i++){
if(a[i]+sum<=lim) sum+=a[i];
else cnt++,sum=a[i];
}
return cnt<=m;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>max_a){
max_a=a[i];
}
sum_a+=a[i];
}
int l=max_a,r=sum_a;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
2.防具布置
【题目描述】
现在有N组防具。
我们可以认为防线是一维的，那么每一租房句读分布在防线的某一段上，并且同一组防具是等距离排列的。
也就是说，我们可以用三个整数S,E和D来描述一组防具，即这一组防具布置在防线的S、S+D、S+2D、...、S+kD(k是整数，S+kD<=E<S+(k+1)D)位置上。
若一个位置上的防具数量为奇数，则我们称这个位置有破绽，但是整个防线上有且仅有一个位置有破绽或根本没有破绽。请你求出破绽的位置或确定防线没有破绽。
【输入格式】
第一行是一个整数T，表示有T组互相独立的测试数据。
每组数据的第一行是一个整数N。
之后N行，每行三个整数Si,Ei,Di，代表第i组防具的三个参数，数据用空格隔开。
【输出格式】
对于每组测试数据，如果防线没有破绽，输出一行“There's no weakness.”。
否则在一行内输出两个空格分隔的整数P和C，表示在位置P有C个防具。
【样例】
输入：
3
2
1 10 1
2 10 1
2
1 10 1
1 10 1
4
1 10 1
4 4 1
1 5 1
6 10 1
输出：
1 1
There's no weakness.
4 3
【思路】
可记1~i位置上共有Si个防具，则若S(2^31-1)为偶数防线无破绽。
若为奇数，可将整个防线分成两段，若左段为奇数则破绽在左段，否则在右段。于是就可以一直分下去直到定位到破绽的位置。
注：这道题由于数据范围一定要开longlong，但开longlong不是说出来就行了而是要在每一个应该开lojnglong的地方都开longlong。还要注意%lld而不是%d
【代码】
#include<bits/stdc++.h>
using namespace std;
const int M=200001;
int n;
int s[M],e[M],d[M];
inline int read(){//快读
register int x=0,f=1;
register char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int S(int x){
int ans=0;
for(int i=1;i<=n;i++){
if(s[i]<=x) ans+=(min(x,e[i])-s[i])/d[i]+1;
}
return ans;
}
void work(){//战线共2^31长
if(S(2147483647)%2==0){
printf("There's no weakness.\n");
return ;
}
long long l=0,r=2147483647;
while(l<r){
long long mid=(l+r)>>1;
if(S(mid)%2==1) r=mid;
else l=mid+1;
}
printf("%lld %lld\n",l,S(l)-S(l-1));
return ;
}
int main(){
int T;
T=read();
for(int t=1;t<=T;t++){
n=read();
for(int i=1;i<=n;i++){
s[i]=read();e[i]=read();d[i]=read();
}
work();
}
return 0;
}
3.最大均值
【题目描述】
给定正整数序列A，求一个平均数最大的，长度不小于L的（连续的）子段。
【输入格式】
第一行两个整数N和L。
接下来N行，每行输出一个正整数Ai。
【输出格式】
输出一个整数，表示平均值的最大值乘以1000再向下取整之后得到的结果。
【样例】
输入：
10 6
6 4 2 10 3 8 5 9 4 1
输出：
6500
【思路】
可选择一个平均值，让序列中的每一个数减去这个值，若存在一个长度不小于L的子段和非负，则增大平均值直到不符合题意。
【代码】
#include<bits/stdc++.h>
using namespace std;
int n,L;
const double eps=1e-5;//精度
double a[100001],b[100001],s[100001];
bool check(double num){
for(int i=1;i<=n;i++) b[i]=a[i]-num;
for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
double ans=-1e10;
double Min=1e10;
for(int i=L;i<=n;i++){
Min=min(Min,s[i-L]);
ans=max(ans,s[i]-Min);
}
return ans>=0;
}
int main(){
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
double l=-1e6,r=1e6;
while(l+eps<r){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.0lf\n",r*1000);
return 0;
}