洛谷P2678跳石头题解

题目

这个题也是一个很经典的题了。其主要思想也是二分答案，原因就是题目中只要出现最大值最小或最小值最大，这种描述十有八九就是二分答案。

这个题原题也是让我们求最短的跳跃距离的最大值。

显而易见，最大值肯定要在1到n之间。

所以我们就从1到n二分跳跃距离。这样就可以以log级别的时间复杂度来枚举出最大值。

二分应该都会吧，就是在符合单调性一段区间内以log级时间来给定值的位置或最小的大于给定值的位置，或者最大的小于给定值的位置的一种算法。

那这个题跳跃距离也是符合单调性的，所以我们就可以用二分来快速枚举。

我们先考虑一个问题，对于一个给定距离d，判断是否要达到这个距离的石头数<m,如果可以，那我们试一试在增加一下，如果不行了，就减小，在这个过程中二分。

当然想到二分，这个题也并不是完了，更重要的是判断二分的左边界和右边界问题。

最后总结一下，遇到二分题，它让你求啥，你就二分啥。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define M 50010
using namespace std;
int l, n, m, left, right;
int dis[M], data[M], maxn, sum;
bool check(int pos)
{
    sum = 0;//sum是要移走的石头数
    int last = 0;
    for(int i = 1; i <= n; i++)
    {
        if(data[i] - last < pos)//last是上一次跳的位置，如果从last调到当前位置所用的距离并不够，就把这个石头移走，判断下一个石头，直到可以满足。
        {
            sum++;
            continue;
        }
        last = data[i];
        
    }
    if(sum > m)//到最后判断如果要跳这个距离，所用的石头数有没有超出限制。
            return false;
    return true;
}
int main()
{
    scanf("%d%d%d", &l ,&n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &data[i]);
    data[n + 1] = l;
    int left = 0,right = l;
    while(left <= right)
    {
        int mid = (left + right) >> 1;
        if(check(mid))//当不超出限制，我们就试试再大的距离可不可以
        {
            maxn = mid;
            left = mid + 1;
        }
        else//当超出限制了，我们就看看小了可以吗 
            right = mid - 1;
    }
    printf("%d", maxn);
}