P2678-跳石头 - 从萌新到萌新的成长历程

题目传送门

题目思路

先找出最大和最小距离，二分查距离就可以了

坑：

1.数组本质上应该多开一个，将L直接作为多出来的最后一个石头加进去，不然会有个点错误

2.N和M可能为0，也就是说不能撤石头，要判断，不然会RE或者WA

AC代码

#include <iostream>
#include <vector>

using namespace std;

#define ll long long

int main()
{
    ll lj, n, m;
    cin >> lj >> n >> m;
    if(n==0)
    {
        cout<<lj<<endl;
        return 0;
    }
    vector<ll> a(n+1);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    a[n]=lj;
    ll l = lj;
    ll r = a[0];
    for (int i = 1; i <= n; i++)
        if (a[i] - a[i - 1] > r)
            r = a[i] - a[i - 1];
        else if (a[i] - a[i - 1] < l)
            l = a[i] - a[i - 1];
    int re = 0;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        ll cnt = 0;
        ll last = 0;
        for (int i = 0; i <= n; i++)
        {
            if (a[i] - last < mid)
                cnt++;
            else
                last = a[i];
        }
        if (cnt <= m)
        {
            l = mid + 1;
            re = mid;
        }
        else
            r = mid;
    }
    cout << re << endl;
    return 0;
}