题解 | #[USACO 2009 Dec S]Music Notes#

在做这个题的时候思路跑偏，考虑的太复杂，然后一开始看到题目中描述的是，接下来的n行是第i个点到起点的距离，我就想起了前缀和，于是就将每个两个之间的距离计算出来了，然后对这些距离进行排序，完全没有思路，在看到别人写的题解和思路时，发现自己想的太复杂了。就是单纯的将与起点的距离最大和与起点的距离最小作为最左边和最右边的值，然后求中位数，以该中位数为当前的最佳答案进行判断，设now的初始值为0，判断第i个石头与now的距离，如果距离小于now就将石头移除，否则将第i个石头作为当前的now遍历接下来的石头。如果移动的石头是大于指定的次数的，则证明当前的最佳距离太大。

#include<iostream>
using namespace std;
int  l,n,m;
int a[1000010];
bool check(int mid)
{
    int  count =0;
    int now =0;
    for(int i=1;i<=n+1;i++)
    {
        if(a[i] - a[now] < mid)
        {
            count++;
        }
        else
        {
            now = i;
        }
    }
    if(count <= m)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1] = l;
    int a=0,b=l;
    int ans =0;
    while(a <= b)
    {
        int  mid = (b+a)/2;
        if(check(mid))
        {
            a = mid+1;
            ans = mid;
        }
        else b = mid-1;
    }
    cout<<ans;
    return 0;
}