二分查找:这有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;
}
你们也可以去洛谷题单里练练:
二分查找与二分答案