跳石头原题

这一题我一开始想的是这么做：

#include <iostream>
#include <cstdio>
#include <algorithm>

#define ll long long

using namespace std;

ll L , N , M , l , r , mid , ans , D[50003] , tmp , last;

int main()
{
    scanf("%lld%lld%lld" , &L , &N , &M);

    r = L;

    for (ll i = 1 ; i <= N ; i++) scanf("%lld" , &D[i]);

    while (l <= r)
    {
        tmp = 0;
        last = 0;
        mid = ((r-l)>>1)+l;

        for (ll i = 1 ; i <= N  ; i++)
        {
            if (D[i] - last < mid) tmp++;
            else last = D[i];
        }

        if (tmp <= M)
        {
            ans = mid;
            l = mid+1;
        }
        else r = mid-1;
    }

    printf("%lld" , ans);
    return 0;
}

但是只有30分，因为没有考虑最后一到终点的跳跃。

后来我看了题解，改成了这样：

#include <iostream>
#include <cstdio>
#include <algorithm>

#define ll long long

using namespace std;

ll L , N , M , l , r , mid , ans , D[50003] , tmp , last;

int main()
{
    scanf("%lld%lld%lld" , &L , &N , &M);

    r = L;

    for (ll i = 1 ; i <= N ; i++) scanf("%lld" , &D[i]);

    D[N+1] = L;

    while (l <= r)
    {
        tmp = 0;
        last = 0;
        mid = ((r-l)>>1)+l;

        for (ll i = 1 ; i <= N + 1 ; i++)
        {
            if (D[i] - last < mid) tmp++;
            else last = D[i];
        }

        if (tmp <= M)
        {
            ans = mid;
            l = mid+1;
        }
        else r = mid-1;
    }

    printf("%lld" , ans);
    return 0;
}

其实就是把终点也看成一块可以移动的石头了，但这也意味着终点的石头可以被移走，那么为什么还能过呢？