寒假集训一期总结(二)––二分查找和二分答案

二分查找

定义

详见百度百科:百度百科-验证

参考代码 

int Binary_Search(int a[],int n,int key){
    int left,right,mid;
    left=1,right=n;
    while(left<=right){
        mid=(left+right)>>1;//相当于/2
        if(key<a[mid]){
            right=mid-1;//折半
        }else if(key>a[mid]){
            left=mid+1;//折半
        }else{
            return mid;//如果等于就返回
        }
    }
    return -1;//没找到
}
           

查找-洛谷P2249

解题思路

本题主要考查了最基础的二分查找,根据上面的定义吧代码敲打出来就可以了

参考代码

#include<iostream>
using namespace std;
int n,b,a[10000005];
int m,ans[10000005]; 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int left,right,mid;
	for(int i=1;i<=m;i++){
		cin>>b;
		left=1,right=n;
		while(left<=right){
			mid=left+(right-left)/2;
			if(b>a[mid]){
				left=mid+1;
			}else if(b<=a[mid]){
				right=mid-1;
			}
			if(a[left]==b){
				ans[i]=left;
				break;
			}
		}
		if(ans[i]==0){
			ans[i]=-1;
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
           

 STL与二分查找

upper_bound这个函数主要是来查找第一个大于

lower_bound这个函数主要是来查找第一个大于等于

两个函数的具体使用格式如下

lower_bound(起始下标,结束下标,查找元素)-数组;
upper_bound(起始下标,结束下标,查找元素)-数组;
           

二分查找下界

 解题思路

本题可以使用我们刚刚讲过的函数

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cin>>m;
	int j=lower_bound(a+1,a+n+1,m)-a;
	cout<<j;
	return 0;
}

           

 二分答案

愤怒的牛

 解题思路

为了让牛间隔的越远越好,那么问题的期望是最小的距离最大化,所以这是一个典型的用二分查找求最大最小值的问题.

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=1000005;
long long n,m,a[MAX],maxn=LONG_LONG_MIN;
long long sum,ans;
bool check(long long mid){
	int cnt=1,sum_c=0;
	for(int i=1;i<=n;i++)
		if(a[i]+sum_c>mid)
			sum_c=a[i],cnt++;
	return cnt<=m;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		maxn=max(maxn,a[i]);
	}
	//sort(a+1,a+n+1);
	long long l=maxn,r=sum,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}
           

跳房子

解题思路 

 这道题是典型的二分答案思维训练的题目

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=1000005;
long long d,n,k,x[MAX],s[MAX];
long long dp[MAX],cnt,sum,ans=-1;
long long read(){
	char c;
	long long s=0,f=1;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*f;
}
bool check(long long mid){
	long long minn=max(1ll,d-mid);
	long long maxn=d+mid;
	dp[0]=0;
	for(long long i=1;i<=n;i++){
		dp[i]=LONG_LONG_MIN;
		for(int j=i-1;j>=0;j--){
			if(x[i]-x[j]<minn)
				continue;
			if(x[i]-x[j]>maxn)break;
			if(dp[j]==LONG_LONG_MIN)
				continue;
			dp[i]=max(dp[i],dp[j]+s[i]);
			if(dp[i]>=k)return true;
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	n=read(),d=read(),k=read();
	for(int i=1;i<=n;i++){
		x[i]=read(),s[i]=read();
		if(s[i]>0){
			sum+=s[i];
		}
	}
	if(sum<k){
		cout<<-1<<endl;
		return 0;
	}
	long long l=0,r=1000,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0; 
}