蒟蒻考前攒人品
二分答案的应用范围：
1.一些明显的字眼：最小值最大或最大值最小
2.没有什么明显的方法好来解决，且答案是满足可二分性的，即答案变大变小check起来性质会不一样
二分的思想很简单，时间复杂度为log级的，有时候可以看数据范围来想方法，大概几十万或百万的数据就一般是log级复杂度
下面是二分的巨水板子
while(l<=r) { int mid=(l+r)>>1; if(check(mid)>m) r=mid-1; else l=mid+1; } cout<<r;这个就是个小板子，没什么用，至于什么时候r=mid-1,l=mid+1就自己YY，最重要的使想到二分之后怎么check呢？这就是二分最容易打萎的地方，好的check能大大地降低复杂度那么一般有哪些比较好的check模型呢？让我们来看一下几道二分经典题
1.第一道：noip2011 聪明的质检员----二分，check类型：前缀和维护
题目概述：给定一列数和m个区间和S，要求确定一个w值，令Y=c格码(每个区间大于等于w的数量)*(每个区间大于等于w的v的和);
使得abs(S-Y)最小，也就是使Y最接近S；
分析：
1.该题的目的是要确定一个w的使得对C格码(每一个区间里>=w的数量)*(>=w的v的和)与 一个给定的S最为接近 2.显然w是满足可二分性的，所以可以二分w，求出那个Y，使其与S接近 3.那么二分了w之后怎么check出Y来 4.区间里>=w的数量和>=w的v的和显然可以用前缀和(用两个)维护(O(n)); 5.然后对于每段区间就可利用前缀和相减再相乘求出区间里的值，然后累加 6.如果Y<S,r=mid+1,然后每次求出来的abs(S-Y),和ans取min 7.最后输出ans；
大水题就直接上标程了(最难得地方好像是看懂c格码)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; long long gi() { long long x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } struct sb { long long v,w; }p[1000000]; struct zz { long long l,r; }e[1000000]; long long tot[1000000],w[1000000],ans=999999999999999999ll,n,m,S; long long check(long long mid)//check二分出来的w { long long Y=0; for(long long i=1;i<=n;i++) { tot[i]=tot[i-1],w[i]=w[i-1];//维护前缀和，开两个，一个计数量，一个计和 if(p[i].w>=mid) { tot[i]+=1; w[i]+=p[i].v; } } for(long long i=1;i<=m;i++) { Y+=(tot[e[i].r]-tot[e[i].l-1])*(w[e[i].r]-w[e[i].l-1]);//这个前缀和应该没什么难度吧 } return Y; } int main() { n=gi(),m=gi(),S=gi(); for(long long i=1;i<=n;i++) { p[i].w=gi(),p[i].v=gi(); } for(long long i=1;i<=m;i++) { e[i].l=gi(),e[i].r=gi(); } long long l=1,r=1ll<<40; while(l<=r)//二分板子 { long long mid=(l+r)>>1; long long Y=check(mid); ans=min(ans,abs(S-Y));//取min if(Y<S) r=mid-1; else l=mid+1; } cout<<ans; }2.第二道：noip 2012 借教室 check类型：差分维护题目大意：该题给出每天的教室数量和订单，要求出对于一些订单(订单就是在s--t的区间里每个点减去一个值)要求订单最早到第几个
会使剩余的教室数量不满足订单
分析：
1.这个第几个订单显然可以满足可二分性，那我们二分到第几个订单不满足 2.那么check时怎么求出到该订单时到底满不满足条件呢？ 3.首先每个订单相当于一个区间修改操作(很有道理吧)，这样我们就可以用差分来实现区间修改O(mid); 4.然后再O(n)的扫一遍每一天现有教室是否满足,这样check就以很优秀的复杂度来判断到这个订单是否满足
这样我又开始上标程了
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cstring> using namespace std; int gi() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } int fre[1000010],cf[1000010],n,m; struct sb { int num,st,ed; }order[1000100]; bool check(int x) { memset(cf,0,sizeof(cf)); for(int i=1;i<=x;i++)//处理差分 { cf[order[i].st]+=order[i].num; cf[order[i].ed+1]-=order[i].num; } int t=0;//记这个差分数组的前缀和 for(int i=1;i<=n;i++)//O(n)check每天 { t+=cf[i]; if(t>fre[i])//订单已经不满足了 { return 0; } } return 1; } int main() { n=gi(),m=gi(); for(int i=1;i<=n;i++) { fre[i]=gi(); } for(int i=1;i<=m;i++) { order[i].num=gi(),order[i].st=gi(),order[i].ed=gi(); } int l=1,r=m,ans=0; while(l<=r)//二分板子 { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else ans=mid,r=mid-1; } if(ans) { cout<<-1<<endl<<ans<<endl; } else cout<<0; }3.第三道：r64大神的题 check类型：差分维护题目描述如下：
大猴子有一排n朵花，第i朵花的高度为hi，大猴子有一个长为w的水壶，一次可以浇一段长为w的一段，使这一段的花的高度全部加1，现在又m天，大猴子
每天可以浇一次水，他想知道m天后，他这一排花的最小高度最高是多少？
分析：1.一看到最..最...显然我们可以想到二分；
2.我们显然可以二分出一个最小高度，怎么check呢？
3.即我们需要使每一朵花的高度都要大于等于这个mid，那么我们求出使每个花的高度都要大于等于mid浇花的次数，然后和m比较即可
4.那我们如何快速求出要达成这个mid需要的浇花的次数呢？
5.每一次浇花可以理解为对于长为w的一段区间进行修改，那我们就可以利用差分维护了；显然我们可以做到保证在这朵花前，每一朵花都满足了mid，
如果发现一朵花的高度小于mid，那么后面一段长为w的区间至少要加mid-hi这么多次，那么这时就可以更新差分数组了，且计数器就可以加上mid-hi了
讲着有点悬，直接上标程
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[100010],q[300010]; int n,m,w; int gi() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } bool check(int x) { int sum=0,p=0,now;//sum为计数器 memset(q,0,sizeof(q));//清空差分数组 for(int i=1;i<=n;i++)//差分 { p+=q[i]; now=a[i]+p; if(now<x) sum+=x-now,p+=x-now,q[i+w]-=x-now;//修改差分数组，计数器加 if(sum>m) return 0; } return 1; } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); int l=2000000000,r=0; cin>>n>>m>>w; for(int i=1;i<=n;i++) a[i]=gi(),l=(a[i]<l?a[i]:l),r=(a[i]>r?a[i]:r); r+=m; while(l<=r)//二分板子 { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } cout<<l-1; return 0; }4.第四道：r64大神的题 kth，应该做过吧check类型：数学方法check
普通版应该都会了吧，二分一个答案，看这个数使第几小
1.题解中的check是看每一行有几个比他小，因为这是一个y=k*x的函数所以可以直接算出他在每行排第几
2.优化方法，可以脑补出来这个比mid小的数量是一个反比例函数，还记得r64的另一道求反比例函数求整点数吧，但不过这里横坐标有一个限制即小于等于n，
有没有很熟悉，多加一点处理就行了，上标程了：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; ll n,m,q,k; bool check(ll x) { ll ans=0,p=sqrt(x),i; for(i=1;i<=p&&i<=n;i++) { ans+=x/i; if(ans>=k) return 1; } if(i>=n) return ans>=k; ans=ans*2-p*p; for(i=1;i<=x/n;i++) ans-=(x/i-n); return ans>=k; } int main() { freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); cin>>n>>m>>q; if(n>m) swap(n,m); while(q--) { scanf("%lld",&k); ll l=1,r=k; while(l<=r) { ll mid=(l+r)>>1; if(check(mid)) r=mid-1; else l=mid+1; } printf("%lld\n",l); } return 0; } 第五道题：noip2015 跳石头题目概述：应该都做过了吧，那我就不讲了
分析：由于老师讲过，直接上标程
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int dis[1000000],L,n,m,v[1000000]; int gi() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } int check(int mid) { int tmp=0; int i=0; while(i<=n) { int j=i+1; while(dis[j]-dis[i]<mid&&j<n+2) { j++; } tmp+=j-i-1; i=j; } return tmp; } int main() { L=gi(),n=gi(),m=gi(); for(int i=1; i<=n; i++) { dis[i]=gi(); } dis[n+1]=L; int l=0,r=L+1; while(l<=r) { int mid=(l+r)>>1; if(check(mid)>m) r=mid-1; else l=mid+1; } cout<<r; }noip 2016 rp++;
