手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

学习笔记---二分查找模板与二分答案

时间:2021/5/25 15:44:22|来源:|点击: 次

二分查找:这有2个模板

模板一:

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

模板二:

	while(l<r)
			{
				int mid=l+r+1>>1;  //不加1会死循环
				if(x>=a[mid]) l=mid;
				else r=mid-1;
			}

当然c++是由俩个函数可以代替二分查找的,a为数组名,n为数组的长度,t为要查找的数
lower_bound(a,a+n,t): 返回数组中第一个大于等于t的数的下标
upper_bound(a,a+n,t): 返回数组中第一个大于t的数的下标

二分答案:

二分答案,就是用二分的方法,在可能的答案区间里找出问题的答案,大多数情况下用于求解满足某种条件下的最大(小)值,前提是答案具有单调性,同时也可以理解为是一种倒推方法(先找答案在判断答案是否可行、有没有更优解)。

二分答案可以分为两种题型:

最大值的最小问题:用模板一解题

最小值的最大问题:用模板二解题

那么这是怎么推出来的呢?
我们来看一组数:1,2,4,10,12
然后我们去查找11

模板一会找到12,12为大于等于11的最小值,所以我们可以用模板一去解最大值的最小问题
模板二会找到10,10为小于等于11的最大值,所以我们可以用模板二去解最小值的最大问题

下面来看几个例题:
P2678 [NOIP2015 提高组] 跳石头

/*
最小值最大问题:使用模板二 
二分出一个最短距离,然后判断这距离是否可以更大?
那么要怎么判断呢?
我们可以去判断如果是这个最短距离,要移走多少块石头,如果移走的石头
没有超过限制,那么则是一个合法解,那么也就可以去寻找最短距离更大的值,
否则是一个非法解,即最短距离不可能这么大 
*/
#include <iostream>
using namespace std;

const int N=50010;

int a[N];
int L,n,m;

bool judge(int mid)
{
	int cnt=0;
	int now=0;
	
	for(int i=1;i<n+1;i++)
	{
		if(a[i]-a[now]<mid) cnt++;
		else 
		{
			now=i;
		}
	}
	
	return cnt<=m;
}
int main()
{
	cin>>L>>n>>m;
	
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	} 
	a[0]=1,a[n+1]=L;
	
	int l=0,r=L; 
	while(l<r)
	{
		int mid=l+r+1>>1;
		if(judge(mid)) l=mid;
		else r=mid-1;
	}
	
	cout<<l;
	return 0;
}

P1182 数列分段 Section II

/*
最大值最小问题:使用模板一 
二分出一个每段和的最大值,在判断这个为最大值时能分几段,如果小于等于
限制的段数,则是合法解,即可以继续去寻找最优解,如果大于限制的段数,
则是非法解,则要去寻找合法解(即使每段和变大) 
*/
#include <iostream>
using namespace std;

const int N=1e5+10;

int a[N];
int n,m;

bool judge(int mid)
{
	int t=0;
	int sum=0;
	for(int i=0; i<n; i++)
	{
		if(sum+a[i] <= mid) sum+=a[i];
		else 
		{
			sum=a[i];
			t++;
		}
	}
	t++; //最后一段要记得加上 
	return t<=m;
}
int main()
{
	cin>>n>>m;
	int l=0,r=0;
	
	for(int i=0; i<n; i++) 
	{
		cin>>a[i];
		l=max(l,a[i]);
		r+=a[i];
	}
	
	while(l<r)
	{
		int mid=l+r>>1;
		if(judge(mid)) r=mid;
		else l=mid+1;
	}
	
	cout<<l;
	return 0;
}

你们也可以去洛谷题单里练练:

二分查找与二分答案

Copyright © 2002-2019 某某自媒体运营 版权所有