4.二分和三分

发表于 分类于 ， 本文字数： 2.5k

二分

二分是一个非常常见但是想要精通却很有讲究的一个垃圾 算法，二分的基础用法是在单调序列或单调函数中进行查找（二分查找），因此当问题的答案具有单调性，就可以通过二分把求解答案的问题转换成二分查找答案并判定答案的正确性（二分答案）。我们还可以用三分法去求解单峰函数的极值。

相信基础的二分大家都会，但是写出来二分不代表能A，因为二分的细节尤其重要，对于整数域上的二分，要注意终止边界和左右区间的取舍时的开闭情况，避免溜掉答案或造成死循环。对于实数域上的二分，要注意精度的问题。

整数域上的二分

本文中的二分保证最终答案处于闭区间[l,r]以内，并以l=r作为循环的结束条件

在单调递增序列a中查找>=x的数中最小的一个(即x或x的后继)

1
2
3
4
5
6
7
8
9
int mid=l;
while(l<r){
   mid = (l+r)/2;
   if(a[mid]>=x){
    r = mid;
   }else{
   	l = mid+1;
   }
}

在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱） 

1
2
3
4
5
6
7

while (l < r) {
	int mid = (l + r + 1) / 2;
	if (a[mid] <= x) l = mid; 
	else r = mid - 1;
}

二分的流程：

分析问题，确定左右半段哪一个是可行区间，以及mid 归属哪一半段

根据分析结果，选择r=mid,l=mid+1,mid=(l+r)>>1和l=mid,r=dmi-1,mid=(l+r+1)>>1

二分终止条件是l==r，该值就是答案所在的位置。

在实数域上的二分

实数域二分，设置eps法

一般eps = 10^-(k+2)^ (k是需要保留的位数)

1
2
3
4
5
6
7
8
while(1+eps<r){
   double mid = (1+r)/2;
   if(calc(mid)){
       r = mid;
   } else{
       l = mid;
   }
}

实数域二分，规定循环次数法 

1
2
3
4
5
6
7
8
for (int i = 0; i < 100; i++) {
	if(calc(mid)){
       r = mid;
   } else{
       l = mid;
   }
}

三分

三分求单峰函数极值

有一类函数称为单峰函数，它们拥有唯一的极大值点，在极大值点左侧严格单调上升，在极大值点右侧严格单调下降；或者拥有唯一的极小值点，在极小值点左侧严格单调下降，在极小值点右侧严格单调上升。

为了避免混淆，我们称后一种函数为单谷函数，对于单峰或单谷函数，可以用三分求其极值。

单峰函数f(),函数定义域[l,r] 上取两个点lmid和rmid, l<lmid<rmid<r,把函数分为三段：

如果f(lmid)<f(rmid)则lmid和rmid要么同处于极大值点左侧，要么分别处于极大值点两侧，无论哪种情况，都可以确定极大值点在lmid右侧,可令l=lmid.

如果f(lmid)>f(rmid)则lmid和rmid要么同处于极大值点右侧，要么分别处于极大值点两侧，无论哪种情况，都可以确定极大值点在rmid左侧,可令r=rmid.

如果f(lmid) = f(rmid),对于严格单调的函数，此时取 l = lmid 或者 r = rmid 均可，对于非严格单调的函数，此时三分法不再使用。

二分答案转化为判定

一个宏观的最优化问题也可以抽象为函数，其定义域是该问题下的可行方案，对这些可行方案进行评估得到的数值构成函数的值域，最优解就是评估最优方案（不妨设评估越高越优）。假设最优评分是S，显然对于所有> S >S>S的值，都不存在一个合法的方案达到此评分，否则就与S的最优性矛盾，而对于所有的< S <S<S，一定存在一个合法方案达到或超过此评分。这样的问题的值域就具有一种特殊的单调性，在S的一侧合法，另一侧不合法，就像一个在( − ∞ , S ] (-\infty, S](−∞,S]上为1，在( S , ∞ ) (S, \infty)(S,∞)上值为0的分段函数，可以通过二分找到这个分界点S。

借助二分，我们把求解最优解问题，转化为给定一个值m i d midmid，判断是否存在一个可行方案评分达到mid的问题。

N本书排成一行，已知第i本的厚度是Ai。把它们分成连续的M组，使T最小化。T表示厚度之和最大的一组的厚度。

分析：

定义域：把书划分成M组的方案

值域（评分标准）：厚度之和最大的一组的厚度

假设最终答案为S ：每组<S，分不完，不存在可行的分书方案；每组>S，一定存在一种分书方案使组数不超过M。

分界点：分书可行性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;

int n,m;
int a[50];

//把n本书分m组，每组厚度之和<=size，是否可行
bool valid(int size){
  int group=1,rest = size;
  for(int i=1;i<=n;i++){
    if(rest>=a[i]) rest-=a[i];
    else {group++,rest = size-a[i];}
  }
  return group<=m;
}

//判定每组厚度之和不超过二分的值时，是否可行
int main(){
  cin>>n>>m;
  
  int r=0;  
  for(int i=0;i<n;i++){
    cin>>a[i];
    r+=a[i];
  }
	int l=0; //区间0-sum_of_ai
  while(l<r){
    int mid = (l+r)/2;
    if(valid(mid)) r = mid; else l = mid +1;
  }
  cout<<l<<endl;
}

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏