题解：2018级算法第六次上机 C6-不Nan的过河

题目描述：

样例：

实现解释：

一道因为没排序做了一个小时没做出来的二分答案模板题（手动呲牙）

知识点：

二分答案，最大值最小化

坑点：

排序，judge(mid)函数内计数的实现

其实从最长一步的最小距离就能大致看出：二分答案

因此需要做的就是对0~L这个区间二分查找满足题意的跳跃距离，直到达到终止条件。

唯一需要注意的就是：何时满足条件，二分答案中最重要的judge函数，可以先缕一下：只能跳m步，需要从0跳到L。

有步数限制，因此跳跃仅在不得不跳时进行（减少步数消耗），所以需要一个pre记录上一次的位置，cnt记录跳跃的步数。然后遍历石子的位置即可（注意排序（题目没说有序）和L的添加（L作为第n+1块石子））

最后需要注意的既是，在判断到最后，cnt还不是真正的cnt，因为此时pre还是跳到L前的位置，因此遍历结束后还需要对cnt进行++操作，然后再比较才行。

更具体的实现可在完整代码中查看，去除注释其实很短。

完整代码：

#include<iostream>

#include<algorithm>

using namespace std;

int L,n,m;

long long a[];

bool judge(int x)

{

    //站在岸边

    int pre = a[];

    //记录跳数

    int cnt = ;

    for(int i = ;i<=n;i++)

    {

        //为了尽量少跳几步，得到最大的最小值，因此仅在不得不跳的时候跳

        if(a[i]-pre>x)

        {

            //跳到前一个位置

            pre = a[i-];

            cnt++;

            //提前判断减少时间

            if(cnt>m) return ;

            //如果还是大，说明跳不过来

            if(a[i]-pre>x) return ;

        }

    }

    //跳到岸上

    cnt++;

    //需要的步数太多

    if(cnt>m) return ;

    return ;

}

int main()

{

    ios::sync_with_stdio(false);

    while(cin >> L >> n >> m)

    {

        a[] = ;

        for(int i = ;i<=n;i++)

        {

            cin >> a[i];

        }

        a[n+] = L;n++;

        sort(a,a+n);

        int l = ,r = L,mid;

        while(l<r)

        {

            mid = (l+r)/;

            //二分答案中的judge，1就是能符合条件，0就是不能

            //这里1就是能在当前范围成功，而为了得到最大的最小值

            //应该减少步长，找到恰好跳到对岸的长度

            if(judge(mid)) r = mid;

            //如果不能则就扩大步长

            else l = mid+;

        }

        cout << r << '\n';

    }

    return ;

}

巴特西

题解：2018级算法第六次上机 C6-不Nan的过河

题目描述：

样例：

实现解释：

完整代码：

最新文章

热门文章