欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分答案

程序员文章站 2022-03-11 20:52:59
...

基本算法 二分答案 《跳石头》

这是一道经典题目,出处为noip2015,也就是我参加OI的第一年

题目描述

一年一度的“跳石头”比赛又要开始了! 

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。 

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。

输入描述:

输入文件第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。 

接下来N行,每行一个整数,第i行的整数Di(0 < Di < L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。 

输出描述:

输出文件只包含一个整数,即最短跳跃距离的最大值。

数据约定:

对于20%的数据,0≤M≤N≤10。 

对于50%的数据,0≤M≤N≤100。

对于100%的数据,0≤M≤N≤50,000,1≤L≤1,000,000,000。

本文不讲述20分,70分做法

  • 本题的正解是使用二分答案。所谓二分答案,就是从答案入手去解决问题,有的时候由题目正推不好得到答案,或者是复杂度太高。恰巧输出要求是一个数值,那么我们可以从数值回推,验证是不是答案即可。
  • 二分是对于寻找答案的描述。即我们知晓了数据范围,或者答案可能存在的范围,从而用二分法去缩小答案的范围,最终确定答案。

对于本题的思路:

1.答案输出一个整数,因此我们从最小距离的最大值下手。
2.L即河的宽度是从0到1000000000,因此我们的答案可能是从0到1000000000
3.那我们写一个二分好了
4.我们写一个check函数,参数是我们二分中的mid,返回的是根据答案推出拿掉的石头数量

 int check(int ans){
    /* ... */
    return tot;
 }

5.那函数怎么写呢?我们从题目输入的数据来看,很像是给了我们一串前缀和!因此我们任意两个石头之间的距离就可以表示成前缀和的差值。我们从出发点(注意不是第一块石头)开始计算,如果两个石头之间的距离小于我们之前给定的答案,就拿掉下一块石头,然后继续判定(这里显然是一个while循环)。然后返回我们拿掉的石头总数。
6.这次我们又回到main函数了,我们每一个拿到的“答案”都对应了一个拿掉的石头数。那么答案是哪一个?题目给定了拿掉石头的最大值,那么就是最接近这个值的答案啦!

AC代码(每个数据点不超过20ms):

#include<cstdio>
#include<algorithm>
#include<iostream>
#define maxn 50010
using namespace std;
int n,m,l; 
int a[maxn];
int check(int t){
    int re=0,now=0;
    while(now<=n){
        int len=a[now+1]-a[now];
        if(len>=t){
            now++;
            continue;
        }
        while(len<t){
            if(now+2<=n+1){
                len=len+(a[now+2]-a[now+1]);
                re++;
                now++;
            }
            else{
                now++;
                re++;
                break;
            }
        }
        now++;
    }
    return re;
}
int main(){
    scanf("%d%d%d",&l,&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    a[n+1]=l;       
    int head=1,tail=1000000000; 
    int mid,ans=0;
    while(head<tail){
        mid=(tail+head)/2;
        if(mid==head) break;
        int p=check(mid);
        if(p>m)
            tail=mid;
        else {
            if(mid>ans) ans=mid;
            head=mid;
        }
    }
    printf("%d",ans);
    return 0;
}


本文代表个人思路以及见解,欢迎广大OIer进行指正。最后祝各位OIer武运昌隆。

二分答案

相关标签: 算法