快乐地打牢基础（1）——二分与三分

本文主要是介绍快乐地打牢基础（1）——二分与三分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分是一种常用且非常精妙的算法，常常是我们解答问题的突破口。二分的基本用途是在单调序列或单调函数中做查找操作。因此当问题的答案具有单调性时，就可以通过二分把求解转换为判定（根据复杂度理论，可知判定的难度小于求解），这使得二分的应用变得广泛。进一步地，我们还可以通过三分法解决单调函数的极值以及相关问题。

一、二分

---

二分法，在一个单调有序的集合或者函数中查找一个解，每次分为左右两部分，判断解在哪个部分并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间，因此效率很高。

例如，在对实数区间$[l,r]$内递增的连续函数$f(x)$,求$[l,r]$内$f(x)$的零点J。J称为$f(x)$在$[l,r]$内的零点，当且仅当满足：
$$\forall L\le x<J,f(x)<0$$$$\forall J<x\le R,f(x)<0$$ $$f(J)=0$$

二分法的思想是不断将待求解区间平均分成两份，根据区间中点的情况来确定目标元素所在的区间，这样把解的范围缩小了一半。

设当前的求解区间为$[l,r]$，其中点为$mid=\frac{l+r}{2}$，则有：

• 若$f(m)<0$，则$J\in [l,mid]$，

• 若$f(m)>0$，则$J\in [mid+1,r]$

• 若$f(m)=0$，则$J=mid$

使用二分法解决类似问题的时候，类似于在思考一个布尔表达式$E$，在问题定义域$[L,R]$内存在一个分界点$J$:
$$\forall L\le x\le J,E(x)=true$$ $$\forall J<x\le R,E(x)=false$$
若求解的问题的定义域为整数域，对于长度为N的求解区间，算法需要$lo{g}_{2}N$次来确定出分界点。

对于定义域在实数域上的问题，可以用类似的方法，判断$R-L$的精度是否达到要求，即$R-L\ge eps$（esp 代表epsilon 无穷小，就是 $ϵ$），但由于实数运算带来的精度问题，若esp取得太小就会导致程序死循环，因此往往指定二分的次数更好。

二分算法的时间复杂度为：$O$（二分次数$\times$单次判断的复杂度）。

二、 二分写法

---

1.整数域上的二分

/*在递增单调数组中找到值为x数字排名*/
//判断函数
bool check(int mid){if(x < a[mid])return false;elsereturn true;
}
//整数域上的二分
int Erfen(int l,int r) {int mid;while(l <= r) {mid = (l+r)>>1;cout<<"l = "<<l <<" mid = "<<mid<<" r = "<<r<<"\n";if(check(mid)) l = mid+1;else r = mid-1;}return r;
}

2.实数域上的二分

//实数域上的二分
double Erfen1(double l,double r) { //dlt = 0.001 (根据题目要求决定精度)double mid;while(fabs(l-r) > dlt) {mid = (l+r)/2.0;if(check1(mid)) r = mid;else l = mid;}return l;
}

三、二分常见的模型

1.二分答案

最小值最大（或最大值最小）问题，这类双最值问题常常使用二分法求解，也就是确定答案后，配合贪心、DP等其他算法检验这个答案是否合理，将最优化问题转换为判定性问题。例如，将长度为n的序列$a_i$分成最多m个连续段，求所有分法中每段和的最大值最小是多少。

【例题1】：BZOJ 1734: [Usaco2005 feb]Aggressive cows 愤怒的牛
整数域的二分实验

题意
在一条直线上有n个点，从n个点中选出m个点，使得最近的两个点的距离最大。

思路
使用贪心，将n个点按编号递增排序。排好序后，把一头牛放在第一个位置。

为什么不是第二个？如果存在第二个开头且满足条件的d，那么把放在第二位置的牛放在第一个位置，d可能会变大。

之后，枚举两头牛之间的最小距离$d$，当把第$i$头牛放在位置$j$上时，那么第$i+1$头牛就要放在放在满足$j+d\le k$的最小的$k$位置上。

因为放在最小的$k$上，才能为后边的牛留下更多的空间，如果随意取的话，原本能放下两头牛的长度，可能不取最小值就放不下了。

例如：
m = 3，d = 1时，如果选取1,3,5就可以满足，但是如果选了1,4就无法满足。

那二分用在哪里？

二分用在枚举两头牛之间的最小距离$d$，如果是使用朴素的线性枚举。$d$要从$x_1$一直枚举到$x_n$,最差情况要枚举 1,000,000,000次，每次判断合法又要进行n次，时间复杂度是$O(n^2)$。
而使用二分来枚举，时间复杂度就降到了$O(nlogn)$。

#include <bits/stdc++.h>
using namespace std;const int Max = 1e5+10;
int n,m,x[Max];
//如果d可以满足题意返回true 
bool check(int d){int cow = 1;int last = x[1];for(int i = 2; i <= n; i++){if(x[i] >= last + d){cow++;last = x[i];}elsecontinue;}return cow >= m;
}
int main(){scanf("%d %d",&n,&m);for(int i = 1; i <= n; i++) scanf("%d",x + i);sort(x+1,x+n+1);//先排序int l = 0,r = x[n] - x[1];while(l <= r){int mid = (l+r)>>1;if(check(mid)) l = mid+1;//如果d可以满足条件就往比d大的方向找 else r = mid-1;//否则向比d小的方向找 }printf("%d\n",r);return 0;
}

【例题2】: POJ 2018 Best Cow Fences
实数域的编程实验
题意：
给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。
思路：
二分枚举每个实数值，判断
“是否存在一个长度不小于L的子段，平均数不小于我们枚举的数”。
如果把数列中的每个数都减去二分的值，就转化为判定
“是否存在一个长度不小于L的子序列的和非负”。
如果存在就向比二分的值大的区间去找，否则向小的区间找。
下面就只剩下如何判定：“是否存在一个长度不小于L的子序列的和非负”需要解决了

这其实是一个经典的最长连续和的问题，只不过加上了长度要不小于L的限制，这也很容易，没有长度限制的时候从1开始，现在只需要从第L个数开始就行了。
最长连续和问题，本题主要采用前缀和相减来解决：

$s_i$代表$A_1$~$A_i$的前缀和。
m a x i − j > = L { A j + 1 + A j + 2 + . . . + A i } = m a x L < = i < = n { s i − m i n 0 < = j < = i − 1 { s u m j } } max_{i-j>= L} \{A_{j+1}+A_{j+2} +...+A_{i}\} = max_{L<= i <= n} \{ s_{i}-min_{0<=j<=i-1}\{sum_{j}\}\} maxi−j>=L​{Aj+1​+Aj+2​+...+Ai​}=maxL<=i<=n​{si​−min0<=j<=i−1​{sumj​}}
接下来只要通过这个式子计算出一个长度不小于L的子序列的和就可以了。

#include <bits/stdc++.h>using namespace std;
const int Max = 1e5 + 10;
double a[Max],b[Max],s[Max];
int n,L;
double eps = 1e-5;
int main(){scanf("%d %d",&n,&L);for(int i = 1; i <= n; i++) scanf("%lf",a+i);int mid;double l = -1e6;double r = 1e6;//开始二分 while(r-l > eps){//因为最后答案要乘1000，所以精度设定在 1e-5 s[0] = 0;double mid  = (l+r)/2.0;double ans = -1e9;double minx = 1e9;for(int i = 1; i <= n; i++){b[i] = a[i] - mid;//减去二分的值 s[i] = b[i] + s[i-1];// 计算前缀和 }for(int i = L; i <= n; i++){//记录下i前面前缀和的最小值 minx = min(minx,s[i-L]); //最大连续和就是s[i]-minx里最大的 ans = max(ans,s[i]-minx); }if(ans >= 0) l = mid;// 存在不小于L且和为非负的子序列 ,向右找 else r = mid;//不存在向左找 //cout<<"l = "<<l<<" r = "<<r<<" ans = "<< ans<<"\n";}printf("%d\n",(int)(r*1000)); return 0;
} 

关于二分答案的总结
Ⅰ.解决最大值最小化（最小值最大化问题）。

Ⅰ.二分答案是假设存在一个正确答案，然后用二分思想来优化蛮力枚举，一步一步的去验证答案的正确性，然后找到一个最小（大）化的正确结果。

Ⅲ.其重点在于对二分结果的判别部分，也就是check函数，它决定了二分策略的方向。普遍是满足check的条件就向我们的目标方向进行更深一步的判别。

2.二分查找

用具有单调性的布尔表达式求解分界点，比如在有序数列中求数字x的排名。

此部分已经在二分写法举过例子了。

3.替代三分

有时，对于一些单峰函数，我们可以用二分导函数的方法求解函数极值，这是通常将函数的定义域敌营为整数域求解比较方便，此时dx可以直接取整数1。

四、三分法

---

三分法适用于求解凸性函数的极值问题，二次函数就是一个典型的单峰函数。

凸性函数
在函数f(x)的图象上取任意两点，如果函数图象在这两点之间的部分总在连接这两点的线段的上方，那么这个函数就是凸函数。
单峰函数
单峰函数是在所考虑的区间中只有一个严格局部极大值(峰值)的实值函数。如果函数f(x)在区间[a, b]上只有唯一的最大值点C，而在最大值点C的左侧，函数单调增加；在点C的右侧，函数单调减少，则称这个函数为区间[a, b]上的单峰函数。

三分法和二分法一样，它会不断的缩小答案所在的求解区间。二分法利用的是函数的单调性，三分法利用的是函数的单峰性。

设当前求解的区间为$[L,R]$,令$m_1=l+\frac{r-1}{3}$,$m_2=r-\frac{r-1}{3}$,接着我们计算这两个点的函数值$f(m_1),f(m_2)$之后，我们将两点中函数更优的那个点称为好点（如果计算最大值，则f更大的那个点就为好点，计算最小值就是小的那个点是好点），函数较差的那个就是坏点。

我们可以证明，最优点与好点 会在坏点的同侧。如图

$f(m_1)>f(m_2)$，因为求最大值，$m_1$是好点，而$m_2$是坏点，因此最后的最优点会与$m_1$一起在$m_2$的左侧，即我们求解的区间由$[L,R]$变成了$[L,m_2]$。根据这个结论，我们可以不停缩小求解的区间，直至得出近似解。

与二分一样我们可以指定三分的次数，或是根据r-l的值来终止算法。
参考程序：

//以求单峰函数的最大值为例
double  Sanfen(double l,double r){l = 0;r = 1e9;while(r - l > 1e-3){double m1 = l + (r-l)/3,m2 = r - (r-l)/3;if(f(m1) < f(m2)) l = m1;else r = m2;}
}

注意：我们介绍单峰函数的时候，特别强调了“严格”单调性。若在三分过程中遇到$f(m_1)=f(m_2)$,当函数严格单调时，令$l=m_1$或$r=m_2$均可。如果函数不严格单调，即在函数中存在一段函数值相等的区间，我们将无法盘点定义域的左右边界应该如何缩小，三分法就不再使用。
【例题】一本通OJ 1435：曲线
题意：

明明做作业的时候遇到了n个二次函数$S_i(x)$= ax^2 + bx + c，
他突发奇想设计了一个新的函数$F(x)=max(S_i(x))$),i = 1…n.。
明明现在想求这个函数在[0,1000]的最小值，要求精确到小数点后四位四舍五入。

思路： 题目给出函数Si(x)的a都是非负的，所以a > 0时，函数是开口向上的二次函数，（a = 0时是一次函数）。
也就是说函数S要么是一个先单调递减再单调递增的下凸函数，那么就是一个单调的一次函数。由此可知$F(x)=max(S_i(x))$是严格单调的，即不存在一段函数值相等的区间。使用三分法。

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e4+10;
const double eps = 1e-9;
int cas,n;
double a[Max],b[Max],c[Max];
double maxx = -1e9;
//用于计算f(x) = max(si(x));
double f(double x){maxx = -1e9;for(int i = 1; i <= n; i++)maxx= max(maxx,a[i]*x*x + b[i]*x + c[i]);return maxx; 
}
double  Sanfen(double l,double r) {while(r - l > eps) {//考虑到精度问题 esp可以开的尽量小一些double m1 = l + (r-l)/3,m2 = r - (r-l)/3;if(f(m1) >= f(m2)) l = m1;//如果m2的函数值小于等于m1的，那么m2是好点，答案应该在[m1,r] else r = m2;//反之在[l,m2] }printf("%.4lf\n",f(l));
}
int main() {scanf("%d",&cas);while(cas--) {getchar();scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%lf %lf %lf",a+i,b+i,c+i);double l = 0,r = 1000;Sanfen(l,r);}return 0;
}

关于三分法的一些总结：
Ⅰ.三分法主要用于处理凸性函数的最值问题；

Ⅱ.三分法使用的前提是函数必须是“严格”单调，即不存在一段函数值相等的区间。

【课后练习】
一本通OJ

1436 数列分段II
1437 扩散
1438 灯泡
1439 【SCOI2010】传送带
完全照抄一本通
参考资料：黄新军 董永建等《信息学奥赛一本通·提高篇》

这篇关于快乐地打牢基础（1）——二分与三分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---