备战校赛(4)


知识点整理(4)二分查找与二分答案

二分,一个看似简单却在细节部分折磨死人的东西。

基础知识点

  • 应用前提:要求表中元素以及所求答案按关键字单调有序排列。
  • 两者面向的大概问题:在一个有序序列中查找一个想要的数。

二分查找

二分查找的细节大概有三点:

  1. while循环的结束条件到底是left小于right,还是小于等于。
  2. (l=mid+1 or l=mid) and (r=mid-1 or r=mid)
  3. 计算 mid 时需要技巧防止溢出,建议写成: mid = left + (right - left) / 2
  4. 边界为浮点时,循环条件要控制精度,更新区间不能+1(为什么有四点)

对于第一点,我的思路就是,自己把程序在脑中模拟一下,看看最后需不需要将left==right的情况加上(听君一席话了属于是)。
对于第二点的话,主要看mid用不用的上,用得上就要留着,别加1溜了,不过也可以同步用一个变量随时记录当前mid,这样再说。
下面给出一些二分查找的应用场景:

找一个数

最简单的应用,直接上代码,抉择看注释:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1,mid;
        while(l<=r){//这边当等于的时候,此时对应的数还没查找,所以要加上
            mid=(l+r)/2;//错误示范了属于是
            if(nums[mid]==target)return mid;//找到
            else if(nums[mid]>target)r=mid-1;//由于这里mid不是所要找的数就没用了,所以不用包括mid
            else l=mid+1;
        }
        return -1;//没找到
    }
};

找左边界

例子:找序列中大于某个数的第一个数

//并非完全适用请具体问题具体分析
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size == 0||nums[nums.size()-1]<=target) return -1;
        int l=0,r=nums.size()-1,mid;
        while(l<r){//这边当等于的时候,此时对应的数已经被check过了,所以不用加上
            mid=l+(r-l)/2;//改错就改了属于是
            if(nums[mid]>target)r=mid;//由于这里mid可能是所要找的数,所以需要包括mid
            else l=mid+1;
        }
        return r;
    }
};

//lower_bound和upper_bound真不错真不搓

找右边界

例子:找序列中小于某个数的最后一个数

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size == 0||nums[nums.size()-1]>=target) return -1;
        int l=0,r=nums.size()-1,mid;
        while(l<r){//这边当等于的时候,此时对应的数已经被check过了,所以不用加上
            mid=l+(r-l)/2;//改错就改了属于是
            if(nums[mid]<target)l=mid;//由于这里mid可能是所要找的数,所以需要包括mid
            else r=mid-1;
        }
        return r;
    }
};

二分答案

  • 基本思想:在答案可能的范围内$[L,R]$二分查找答案,检查当前答案是否满足题目的条件要求,根据判断结果更新查找区间。

下面同样给出应用场景:

求最大的最小值

原题链接:洛谷P2678 跳石头

此题是求最大的最短跳跃距离

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 50010;
ll L, N, M;
ll dis[maxn]{0};
bool binary(int x){
    ll pre = 0,num=0;
    for (int i = 1; i <= N;i++){
        if(dis[i]-pre<x){//记录小于最短的,代表要拿开的岩石
            num++;
        }
        else{
            pre = dis[i];
        }
    }
    if(num<=M)
        return true;
    return false;//要拿开的超过了最多岩石的限制
}
int main(){
    cin >> L >> N >> M;
    for (ll i = 1; i <= N;i++){
        scanf("%lld", &dis[i]);
    }
    ll l = 1, r = L,mid,ans=L;
    while(l<=r){//对最短距离进行二分
        mid = (l + r) / 2;
        if(binary(mid)){//检查答案
            ans = mid;//记录ans
            l = mid + 1;//return true代表还可以继续往右边搜索
        } 
        else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}

再来一题:洛谷P1824进击的奶牛

#include<cstdio>
#include<algorithm>
using namespace std;
const int lnf = 1e9;
const int max_N = 100010;
int N[max_N]{0};
int n,m,ans{0};
bool judge(int mid){
    int last{-lnf},count{0};
    for (int i = 1; i <= n;i++){
        if(N[i]-last>=mid){
            last = N[i];
            count++;
        }
    }
    return count >= m;
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n;i++){
        scanf("%d", &N[i]);
    }
    sort(N + 1, N + n);
    int L{0}, R{lnf},mid;
    while(L<=R){
        mid = L + R >> 1;
        if(judge(mid)){
            L = mid + 1;
            ans = max(ans, mid);
        }
        else{
            R = mid - 1;
        }
    }
    printf("%d", ans);
    return 0;
}

求最小的最大值

原题链接:洛谷P1525关押罪犯

此题实则是求最小的最大矛盾值,下面的题解的check函数中使用的是bfs来进行二分图染色,染色成功就返回true,而且下面的二分中涉及到了另外一种二分方式,即通过target的相邻元素是否在答案区间中来判断。

#include<bits/stdc++.h>
using namespace std;

const int maxn=100000+15;
int n,m,sum;
int head[maxn];
struct node{int to;int z;int next;}edge[maxn*2];
inline int read()//快读
{
	char ch;
	int fu=1,x=0;
	for (ch=getchar(); ch<=32; ch=getchar());
	if (ch=='-') fu=-1,ch=getchar();
	for (x=0; ch>32; ch=getchar()) x=x*10+ch-48;
	return x*fu;
}
void add(int x,int y,int z)//存有向图
{
	edge[++sum].next=head[x];
	edge[sum].to=y;
	edge[sum].z=z;
	head[x]=sum;
}
bool bfs(int midd) //bfs进行二分图染色
{
	int color[maxn];
	memset(color,0,sizeof(color));
	queue <int> q;
	for (int j=1;j<=n;j++)
	{
	if (color[j]) continue;
    q.push(j);color[j]=1;
    do
    {
      int k=q.front();q.pop();
	  for (int i=head[k];i;i=edge[i].next)
	  if (edge[i].z>=midd)//矛盾值大于等于所给值就进行二分图染色(题目中表示放在两个监狱)
	  {   
	  	if (color[edge[i].to]==0) {
		   color[edge[i].to]=color[k]==1?2:1;
		   q.push(edge[i].to);
	    }
		else if (color[edge[i].to]==color[k])       return false; //表示染色失败
		}
    }while (!q.empty());
}
    return true;
}
int main()
{
	int maxx;
	n=read();m=read();
	for (int i=1;i<=m;i++)
	{
		int a,b,c;
		a=read();b=read();c=read();
		maxx=max(maxx,c);
	    add(a,b,c);
	    add(b,a,c);
	}
	int l=0,r=maxx+1,midd;
	while (l+1<r)//这里注意!
	{
		midd=(l+r)>>1;
		if (bfs(midd)) r=midd;
		else l=midd;
	}
	printf("%d",l);
	return 0;
}

求满足条件的最大(小)值

原题链接:hdu 1969平均分pie

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const double eps = 1e-10;
const double pi = 4*atan(1.0);
int n,f,arr[10100];
bool check(double r)
{
    double s = r*r;
    int num = 0;
    for(int i=1; i<=n; ++i)
    {
        double tep = arr[i]*arr[i];
        num += (int)(tep/s);
    }
    return num >= f+1? true : false;//f+1因为要分给自己
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>f;
        for(int i=1; i<=n; ++i)
            cin>>arr[i];
        double l = 0.0;
        double r = 10100.0;
        while(fabs(r-l)>eps)  //注意精度,相当于浮点数版本的l<r
        {
            double mid = (l+r)/2.0;
            if(check(mid))
                 l = mid; 
            else r = mid;
        }
        printf("%.4f\n",r*r*pi);
    }
    return 0;
}

文章作者: Wdstql
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Wdstql !
评论
  目录