二分

迈不过友情╰ 2022-01-10 04:37 280阅读 0赞

一、整数集合上的二分

1.  具体问题具体分析，左右半段哪个是可行区间，以及mid归属哪一半
2.  根据分析结果，选择一个配套形式
    
    1.  \\(r=mid,l=mid+1,mid=(l+r)/2\\)
    2.  \\(l=mid,r=mid-1,mid=(l+r+1)/2\\)
3.  二分终止条件 \\(l==r\\)

例题：

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

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

1.  单调递增序列a找到 <=x 的数中最大的一个(即x或x的前驱)

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

tip:

STL lower\_bound和upper\_bound:非降序序列中二分查找x的后继

//lower_bound(二分初始地址，二分结尾地址，要查找的x) 第一次出现大于等于x的地址 //upper_bound(二分初始地址，二分结尾地址，要查找的x) 第一次出现大于x的地址 int a[10]={1,1,1,3,3,5,5,5,5,6}; cout<<k<<"的第一个大于等于它的位置在"<<((lower_bound(a,a+n,k))-a)+1<<endl; cout<<k<<"的第一个大于它的位置在"<<((upper_bound(a,a+n,k))-a)+1<<endl;

二、实数域上的二分

1.  确定精度 一般保留k位小数 取 \\(eps=10^\{-(k+2)\}\\)

while(l + 1e-5 <r){ double mid = (l+r)/2; if(calc(mid)) r = mid;else l = mid; }

1.  精度不容易确定，采取循环固定次数的二分方法，这种方法得到的精度往往比设置eps高

for(int i=0;i<100;i++){ double mid = (l+r)/2; if(calc(mid)) r = mid;else l = mid; }

三、三分求单峰函数极值

1.  单峰函数：拥有唯一的极大值点，在极大值点左侧严格单调上升，右侧严格单调下降
    
    单谷函数：拥有唯一的极小值点，在极小值点左侧严格单调下降，左侧严格单调上升
2.  单峰函数为例：在定义域\[l,r\]上任取两个点lmid,rmid

\\\[ \\begin\{cases\} f(lmid)>f(rmid) 极大值点在rmid左侧 r=rmid\\\\ f(lmid)<f(rmid) 极大值点在lmid右侧 l=lmid\\\\ f(lmid)=f(rmid) 无法判断，强调严格单调 \\end\{cases\} \\\]

tip: 1. 函数存在一段相等的部分，三分法不再适用

2. 定义域范围每次缩小1/3

四、二分答案转化为判定

1.  把求最优解转化为给定一个值mid,判定是否存在一个可行评分达到mid的问题。

例题：

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

分析：

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

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

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

分界点：分书可行性。

题解：

#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; }

1.  **Best Cow Fences(PO2018)**
    
    农夫约翰的农场由一长排N (1 <= N <= 100,000)块地组成。每个土地包含一定数量的奶牛，1 <= ncows <= 2000。想要在一组相邻的牧场周围建一个篱笆，以便最大化该组内每块牧场的平均奶牛数量。每组必须包含至少F (1 <= F <= N)土地，其中F作为输入。在给定约束条件下，计算使平均值最大化的栅栏位置。
    
    输入输出格式：
    
    输入：第一行输入N，F，接下来每一行输入每个土地的奶牛数。
    
    输出：一个整数，它是最大平均值的1000倍。不执行四舍五入，只打印1000\*ncows/nfields的整数。
    
    输入样例：  
    10 6  
    6  
    4  
    2  
    10  
    3  
    8  
    5  
    9  
    4  
    1
    
    输出样例：  
    6500
    
    大意：给定正整数数列A，求一个平均数最大的、长度不小于L的子段。
    
    分析：
    
    判定：是否存在一个长度不小于L,平均数不小于二分的值
    
    前缀和求解一个字段长度不小于L，和最大
    
    题解： 这题容易TLE,注意精度选择和区间缩小
    
        #include<iostream> using namespace std; double a[100001],b[1000001],sum[100001]; int main(){ int N,L; cin>>N>>L; double l = 1e9,r = 0; for(int i=1;i<=N;i++){ cin>>a[i]; l = min(l,a[i]); r = max(r,a[i]); } double eps = 1e-4; while(r-l>eps){ double mid = (l+r)/2; for(int i=1;i<=N;i++) b[i] = a[i] - mid; //减去二分值 求字段和非负 for(int i=1;i<=N;i++) sum[i] = sum[i-1]+b[i];//前缀和思想 double ans = -1e10; double min_val = 1e10; for(int i=L;i<=N;i++){ min_val = min(min_val,sum[i-L]); ans = max(ans,sum[i] - min_val); } if(ans>=0) l = mid; else r = mid; } cout<< int(r*1000)<<endl; return 0; }

转载于:https://www.cnblogs.com/wendiudiu/p/10765870.html