欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分答案算法

程序员文章站 2022-06-02 16:14:19
...

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

简单二分模版:

//第一个大于或等于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
*/