首页 > 代码库 > 关于二分操作的基本应用
关于二分操作的基本应用
前言：二分答案最重要的一点就是答案具有连续性，即有单调性的连续函数。
一：可以验证答案是否正确，来改变答案区间
如：求零点，求最接近元素。
还可以用于某些去掉重复元素的操作。
这一类比较简单，不做详细解释
二：最大化最小值/最小化最大值
如noip2015：
2257: [NOIP2015]跳石头
Description
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M块岩石（不能移走起点和终点的岩石）。
Input
输入第一行包含三个整数L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。 接下来N行，每行一个整数，第i行的整数Di（0 < Di < L）表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
Output
输出只包含一个整数，即最短跳跃距离的最大值。
Sample Input
25 5 2211141721Sample Output
4HINT
样例说明】 将与起点距离为2和14的两个岩石移走后，最短的跳跃距离为4（从与起点距离17的岩石跳到距离21的岩石，或者从距离21的岩石跳到终点）。
【数据规模与约定】 对于20%的数据，0 ≤ M ≤ N ≤ 10。 对于50%的数据，0 ≤ M ≤ N ≤ 100。 对于100%的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。
下面代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int lenth[50001];int len,n,m;bool check(int step){ int count=0,temp=0,i; for(i=1;i<=n;i++) { if(lenth[i]-lenth[temp]>=step) { temp=i; } else count++; } if(count>m) return false; if(len-lenth[temp]<step) return false; return true;}int main(){ int i,j; scanf("%d%d%d",&len,&n,&m); int l=0,r,mid; for(i=1;i<=n;i++) { scanf("%d",&lenth[i]); } r=len; while(l+1<r) { mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } if(check(r)) cout<<r; else cout<<l; }
三：关于二分验证的方法
1.按照题意模拟验证
比较简单不详细说明
2.dp验证
如：
魔棒
时间限制: 1 Sec 内存限制: 128 MB 提交: 50 解决: 8 [提交][状态]题目描述
有一个英雄，初始生命值是hp（生命值无上限），在接下来的n秒内，每秒会受到一次伤害，第i秒受到的伤害值为a[i]。这个英雄有一个道具“魔杖”，魔杖的初始能量为0，每受到一次伤害，积攒一点能量。在英雄受到伤害后，可以立即释放魔棒中的能量，恢复15*[能量点数]的生命值，且魔棒的点数清零。释放能量有施法间隔cd（cd是正整数），即相邻的两次释放的时间间隔至少有cd秒。任何时刻当hp<=0时视为死亡，问这个英雄存活下来的前提下，cd的值最大可以是多少？
注意，若a[i]为负，受到“伤害”后实际上生命值是增加的，魔棒仍然积攒能量。
输入
第一行两个正整数n,hp，含义如题目所述。
第二行n个整数，分别是a[1]..a[n]。
输出
一个数，最大的cd，cd是一个正整数。
如果cd没有上限，输出“No upper bound.”；如果无论如何都不能存活，输出-1。
样例输入
7 3020 5 30 4 10 5 20
样例输出
2
提示
对于30%的数据,n<=12；
对于100%的数据,n<=500，|a[i]|<=1000；
#include<iostream>#include<cstdio>#include<cstring>#define ll long longusing namespace std;ll a[550],hp,dp[501][501][2],sp[501][2],n;bool check(int mid){ memset(dp,0,sizeof(dp)); memset(sp,0,sizeof(sp)); dp[0][0][0]=hp; sp[0][0]=hp; int i,j; for(i=1;i<=n;i++) { for(j=2;j<=i;j++) { dp[i][j][0]=dp[i-1][j-1][0]-a[i]; dp[i][j][1]=dp[i-1][j-1][1]-a[i]; if(dp[i][j][0]>0) { sp[i][0]=max(sp[i][0],dp[i][j][0]+j*15); } if(dp[i][j][1]>0&&j>=mid) { sp[i][1]=max(sp[i][1],dp[i][j][1]+j*15); } } dp[i][1][0]=dp[i-1][0][0]-a[i]; if(dp[i][1][0]>0) { sp[i][0]=max(sp[i][0],dp[i][1][0]+15); } int step=max(sp[i-1][0],sp[i-1][1]); if(step>=a[i]) { dp[i][0][1]=step+15-a[i]; } dp[i][1][1]=step-a[i]; } for(i=0;i<=n;i++) { if(dp[n][i][0]>0||dp[n][i][1]>0) return 1; } return 0;}int main(){ ll i,j; ll count=0; int step=0; scanf("%lld%lld",&n,&hp); ll ppp=hp; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } hp=ppp; for(i=1;i<=n;i++) { hp=hp-a[i]; count++; if(hp<=0&&step==0) { hp=hp+(count*15); step=1; } if(hp>0&&i==n) { cout<<"No upper bound."; return 0; } } hp=ppp; ll l=0,r=n,mid; while(l+1<r) { mid=(l+r)/2; if(check(mid)==1) { l=mid; } if(check(mid)==0) { r=mid; } } if(l==0) cout<<"-1"; else cout<<l;}
dp验证比较常见，不再概述
3.最短路验证
问题 A: 收费站(cost.pas/c/cpp)
题目描述
输入
第一行5个正整数，n，m，u，v，s。分别表示有n个城市，m条公路，从城市u到城市v，车的油箱的容量为s升。
接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。
再接下来有m行，每行3个正整数，ai,bi,ci(1<=ai,bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi,或者从城市bi到城市ai，需要用ci升汽油。
输出
仅一个整数，表示小红交费最多的一次的最小值。
如果她无法到达城市v，输出-1。
样例输入
4 4 2 3 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3
样例输出
8
提示
对于60%的数据，满足n<=200，m<=10000，s<=200
对于100%的数据，满足n<=10000，m<=50000，s<=1000000000
对于100%的数据，满足ci<=1000000000，fi<=1000000000，可能有两条边连接着相同的城市。
代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>#define inf 0X3F3F3F3Fusing namespace std; int n,m,u,v,s,f[10005],dist[10005];vector<int>g[10005],w[10005]; struct data{ int d,id; friend bool operator < (data a,data b) { return a.d>b.d; }}; void Dij(int s,int *d,int limit){ priority_queue<data>pq; for(int i=1;i<=n;i++) d[i]=inf; pq.push((data){0,s}); d[s]=0; while(!pq.empty()) { data t=pq.top(); pq.pop(); int i=t.id; if(f[i]>limit) continue; if(t.d>d[i]) continue; d[i]=t.d; for(int k=0;k<g[i].size();k++) { int j=g[i][k],c=w[i][k]; if(f[j]>limit) continue; if(d[i]+c<d[j]) { d[j]=d[i]+c; pq.push((data){d[j],j}); } } }} int main(){ scanf("%d%d%d%d%d",&n,&m,&u,&v,&s); for(int i=1;i<=n;i++) { scanf("%d",&f[i]); } for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); g[x].push_back(y); g[y].push_back(x); w[x].push_back(z); w[y].push_back(z); } int A=0,B=1000000000,ans; while(A<=B) { int mid=(A+B)/2; Dij(u,dist,mid); if(dist[v]<=s) { B=mid-1; ans=mid; } else { A=mid+1; } } if(B==1000000000) { printf("-1\n"); } else printf("%d\n",ans); return 0;}
验证的方法还有很多，目前遇到的只有这几种，遇到后会再做补充。
关于二分操作的基本应用