noip2015提高组跳石头

P2678

首先，显然答案是满足单调性的。

很容易考虑到二分答案，二分时贪心地抽石头就好了。

最重要的是要特判 $n = 0,m = 0$ 的情况 (也有可能是代码写的不好)

代码:

#include <bits/stdc++.h>
using namespace std;
int L, n, m;
const int N = 500000 + 20;
int a[N];

bool check(int mid)
{
    int tot = 1;
    while (a[tot] < mid)
        tot++;
    tot--;
    for (int i = tot + 1; i <= n;)
    {
        int k = i + 1;
        while (a[k] - a[i] < mid && k <= n + 1)
            k++;
        tot += k - i - 1;
        i = k;
        if (i == n)
            return tot <= m;
        if (i > n)
            return false;
        if (a[n] - a[i] < mid)
            return false;
    }
    return tot <= m;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> L >> n >> m;
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    if((n | m) == 0) 
    {
        cout << L;
        return 0;
    }

    n++;
    a[n] = L;
    l = 0, r = L;

    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l;
    return 0;
}