设置越界下标确定是否存在
1 //>=x 2 while(l<r){ 3 int mid((l+r)>>1); 4 if(a[mid]>=x) r=mid; 5 else l=mid+1; 6 } 7 //<==x 8 while(l<r) 9 { 10 int mid((l+r+1)>>1); 11 if(a[mid]<=x) l=mid; 12 else r=mid-1; 13 } 14 //setprecision(3) 15 while(l+(1e-5)<r) 16 { 17 double mid=(l+r)/2; 18 if(calc(mid)) r=mid; 19 else l=mid; 20 } 21 FOR(i,0,100) 22 { 23 double mid((l+r)/2); 24 if(calc(mid)) r-mid; 25 else l=mid; 26 }
从学oi到现在,二分思想是逐渐发挥其威力的。其思想跟数学归纳法很像:
并不直接解决问题,而是将问题转化为几个相同的规模较小的问题。对于很简单的子问题(边界条件),直接给出答案。
对于高级数据结构,像线段树,平衡树都是基于二分思想
可以说,二分是算法大楼的重要根基之一。
用二分法配合基础算法打暴力,往往会有意想不到的收获。
对于有单调性的序列,二分能够在O(logn)的时间内进行查找。
具体应用:
1. 二分查找
- binary_search(a+n1,a+n2,k);True 找到 ,False 没找到
- Lower_bound(a+n1,a+n2,k[,cmp])
可以排在值的后面
- upper_bound(a+n1,a+n2,k[,cmp])
必须排在值的后面
2、二分答案
对于最大值最小化和最小值最大化的问题,可以二分答案,利用答案倒推。
经典例题
A. tree
给你一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 need 条白色边的生成树
WQS二分
P2619 [国家集训队2]Tree I
https://www.luogu.org/problemnew/show/P2619
1 const int MX=100010;
2 struct edge{int u,v,w,col;}e[MX];
3 int fa[50010];
4 int n,m,k,l,r,mid,ans1,cc,t;
5 void scan()
6 {
7 cin>>n>>m>>k;
8 FOR(i,1,m) {cin>>e[i].u>>e[i].v>>e[i].w>>e[i].col;e[i].u++;e[i].v++;}
9 }
10 bool cmp(edge aa,edge bb)
11 {
12 return aa.w==bb.w?aa.col<bb.col:aa.w<bb.w;
13 }
14 int findf(int x){return fa[fa[x]]==fa[x]?fa[x]:fa[x]=findf(fa[x]);}
15 bool mg(int x,int y)
16 {
17 int t1=findf(x);
18 int t2=findf(y);
19 if(t1==t2) return 0;
20 else {fa[t1]=t2;return 1;}
21 }
22 bool kruskal()
23 {
24 FOR(i,1,m) if(e[i].col==0) e[i].w+=mid;
25 FOR(i,1,n) fa[i]=i;
26 sort(e+1,e+m+1,cmp);
27 t=ans1=cc=0;
28 FOR(j,1,m)
29 {
30 if(mg(e[j].u,e[j].v))
31 {
32 ans1+=e[j].col^1;
33 cc+=e[j].w;
34 }
35 if(t==n-1) break;
36 }
37 return ans1<k;
38 }
39 void work()
40 {
41 l=-105;r=105;
42 while(l<r)
43 {
44 mid=l+r+1 >>1;
45 if(kruskal()) r=mid-1;
46 else l=mid;
47 FOR(i,1,m) if(e[i].col==0) e[i].w-=mid;
48 }
49 mid=l;kruskal();
50 cout<<cc-k*l;
51 }
B. Chebnear
最近,R终于获得了一片他梦寐以求的农场,但如此大的一片农场,想要做好防卫工作可不是一件容易的事。所以R购买了N个守卫,分别让他们站在一定的位置上(守卫不可移动,同一位置上至多有一个守卫)。但是,安排了所有的守卫之后,R才发现,守卫们彼此十分厌恶。经R研究,当某两个守卫距离≤K,他们就会发生争吵;但是,想要守卫们和解也是不难的——只需要R给出的平均工资能使两人满意,他们就会同意和解、成为朋友;当然,如果两个守卫有共同的朋友,他们也会和解成为朋友。R非常不想守卫们争吵,因此他想找出,在能使所有守卫闭嘴的前提下,平均工资的最小值是多少。他想到了一个绝妙的方法,但他忙着去Farm,没时间,所以这个任务就交给你了。
Sort边权值,从小到打拿 二分选边条数,每次判断不在同一联通快中中点的最小距离
4. 三分法
mid1=l+(r-l)/3;mid2=r-(r-l)/3;
对于单峰函数,最优点会与好点在坏点同侧
5. 分治解题
Color zed的刷子宽度只有1,也就是说,一次只能将连续的一排或一列格子涂上颜色(长度任意)。zed想用最少的次数把栅栏全部涂上颜色(注意,一个格子不能重复涂色)
我理所当然的想用DP做,但是有特殊情况
解决办法:每次不断往上垒,碰到中断的地方就分治解决,分别枚举
(其实不需要离散化,>5000的直接丢掉即可)