寒假集訓一期總結(二)––二分查找和二分答案

二分查找

定義

詳見百度百科:百度百科-驗證

參考代碼 

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; 
}