二分答案算法

想要学习二分答案，就必须先会简单二分

简单二分模版：

//第一个大于或等于x的数的下标 
int lower_bound(int x,int n,int a[]){
	int lb=-1,ub=n;
	while(ub-lb>1){
		int mid=(ub+lb)/2;
		if(a[mid]>=x){//如果满足，查找区间缩小到[lb,mid]
			ub=mid;
		}else{
			lb=mid;
		}
	}
	return ub;
}
//第一个小于或等于x数的下标 
int opper_bound(int x,int n,int a[]){
	int lb=-1,ub=n;
	while(ub-lb>1){
		int mid=(ub+lb)/2;
		if(a[mid]<=x){//如果满足,查找区间缩小到[mid,ud]
			lb=mid;
		}else{
			ub=mid;
		}
	}
	return lb;
} 

二分搜索：

核心思想：存在一个分界点，小于分界点的不合法，大于分界点的不如他优

前提：答案区间是单调的

其实与高中数学学的二分法很相似，待求的问题通常答案会求极值，我们可以将所有组成答案的集合进行排序，然后利用二分进行分解
解释：
假设答案区间是[lb,ub]
mid=(lb+ub)/2;
1.求答案最大值：如果mid满足条件，则区间[lb,mid)可以省略，答案最大值只会在[mid,ul]中取值
2.求答案最小值：如果mid满足条件，则区间(mid,ul]可以省略，答案最小值只会在[lb,mid]中取值

如上图，进行二分，舍去不满足条件的区间，留下满足条件的区间，重复以上步骤，就会无限逼近答案，最后在lb或ub就可以取到答案

这样理解比较抽象，结合一道例题理解

砍树

一片森林里有n颗树，每颗树的高度是ai，伐木工需要k长度的木材，伐木工伐木机的锯片高度为h，低于锯片高度的树不砍，高于锯片高度的树则砍掉，求伐木工收集到k长度的树h的最大值（即锯片高度尽量高，但是要收集足够的木材）

这道题正面做很难解决，但是利用二分答案则很简单
首先，锯片高度h最小是0,最大是所有树木最高的那棵树的高度maxtree;即我们的答案只会在[0,maxtree]这个区间中取值，将lb初始为0,ub初始为maxtree,然后不断二分缩小答案集合

如何判断mid是否满足条件，引入一个check()函数进行判断即可
check(mid)=锯片高度为mid时，收集的木材够不够

#include<bits/stdc++.h>
using namespace std;
int N,M,height[1000005],treemax;
//收集的木材够不够 
bool check(int x){
	int sum=0;
	for(int i=0;i<N;i++){
		if(height[i]>x){
			sum+=height[i]-x;
		}
		if(sum>=M)return true;//木材足够，满足条件
	}
	return false;
}
int solve(){
	int lb=0,ub=treemax;
	for(int i=0;i<100;i++){//100次循环可以达到10^-30的精度范围
		int mid=(lb+ub+1)/2;//求中间值
		if(check(mid)){//判断mid是否满足条件，进而划分区间
			lb=mid;
		}else{
			ub=mid-1;
		}
	}
	cout<<ub<<endl;//输出最大值（最大值一定是右边的值）
}
int main(){

	cin>>N>>M;
	for(int i=0;i<N;i++){
		cin>>height[i];
		treemax=max(treemax,height[i]);//求出树最大高度 
	}
	solve();
	return 0;
}

二分搜索解题步骤：

补一句：如果分不清楚lb和ub怎么截取区间，还有不知道最后是输出lb和ub可以画一个单调递增直线进行理解

例题：

#include<bits/stdc++.h>
using namespace std;
const int INF=1000000000;
int n,k;
double a[10000];
bool check(double x){//判断割下的条数够不够
	int LL=0;
	for(int i=0;i<n;i++){
		LL += (int)(a[i] / x);
	}
	return LL>=k; 
}
void bound(){
	double lb=0,ub=INF;//切割长度的最小值，最大值 
	for(int i=0;i<1000;i++){
		//printf("%f %f\n",lb,ub);
		double mid=(lb+ub)/2;
		if(check(mid)){//满足条件,切掉左边，最大值仍然保证在区间[mid,ub] 
			lb=mid;
		}else{
			ub=mid;//不满足条件,切掉右边，最大值在区间[lb,mid] 
		}
	}
	//printf("来了\n");
	printf("%.2f\n",floor(ub*100)/100);
	//return ub;
}
int main(){
	cin>>n;
	cin>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	bound();
	//printf("%.2f\n",floor(ub*100)/100);
	return 0;
}
/*
4
11
8.02 7.43 4.57 5.39
*/

#include<bits/stdc++.h>
using namespace std;
const int INF=999999999;
int n,k,A[100005];
bool check(int x){//判断需要插入的数字次数会不会多余k
	int ans=0;
	for(int i=1;i<n;i++){
			ans+=(A[i]-A[i-1])/x;
			if(ans>k)return false;
	}
	return true;
}
void solve(int maxn){
	int lb=0,rb=maxn;//答案只会在区间[0,maxn]中取值
	for(int i=0;i<100;i++){
		int mid=(lb+rb+1)/2;
		if(check(mid)){
			rb=mid;
		}else{
			lb=mid+1;
		}
		//printf("lb=%d rb=%d\n",lb,rb);
	}
	cout<<lb<<endl;
}
int main(){
	int maxn=INF;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>A[i];
		maxn=max(maxn,A[i]-A[i-1]);//找出最数字之间的最大差值
		
	}
	solve(maxn);
	return 0;
}
/*
测试数据
3 1
100 200 230
5 2
10 13 15 16 17
*/