题目1[NOIP-2015]

题目来源：https://nanti.jisuanke.com/t/T2028

算法思想
1.求最短距离的最大值，果断二分，注意这里将起点，终点都看作石头

for(int i=1; i<=n; i++)
    scanf("%d", &a[i]);
a[n+1]=l;        //将起点、终点都看做石头

2.判断最短距离middle是否可行时，遍历数组，若两两距离小于middle，石头移走++cnt

int lower_bound(int low, int high)    //求解最短距离的最大值
{                    //即二分查找1-l 
    int ans;
    while(low<=high)
    {
        int middle;        //middle为最短距离 
        middle= (low+high)>> 1;
        if(judge(middle))    //judge(middle)为真则继续查找(middle+1)`high
        {
            ans= middle;
            low= middle+1;
        }
        else        //judge(middle)为假则查找low`(middle-1) 
            high=middle-1;
    }
    return ans;
}

bool judge(int x)    //judge()为真则满足：至多移走m个石头，最短距离为x 
{
    int count= 0, now=0;    
    for(int i=1; i<=n; i++)
    {
        if(a[i]- a[now]< x)   //相邻石头间距离若小于x,石头必须移走 
            count++;
        else         
            now= i;
    }          //最终得到count值为至少移走石头个数 
    return count <= m;   //至少移走个数count不大于最多能移走个数m时,为真 
}

题目2[POJ-2456]

题目来源：https://vjudge.net/problem/POJ-2456

算法思想
1.同样求最短距离最大值，无需增加起点终点，注意要排序
2.选择奶牛所在位置，即上题确定石头的位置，那么记录空位置，即上题需要移走的石头数

bool judge(int x)       //judge()为真则满足：放置m头奶牛，最短距离为x 
{
    int now = 0, cnt = 0;
    for(int i = 1; i < n; ++i)
    {
        if(l[i] - l[now] < x)   //相邻距离若小于x,不能放奶牛(石头必须移走) 
        {
            ++cnt;
        }
        else
            now = i;
    }
    return cnt <= (n-m);    //最少空位置数cnt不大于n-m，为真
}

void solve()
{
    sort(l, l+n);
    int low = 0, high = l[n-1] - l[0]+1, ans = -1;
    while(low <= high)
    {
        int middle = (low + high) >> 1;
        if(judge(middle))
        {
            ans = middle;
            low = middle + 1;
        }
        else
            high = middle - 1;
    }
    printf("%d\n", ans);
}