[数据结构与算法]小biu放牛（二分答案）

题目描述

小Biu最喜欢的活动就是放牛，但是由于他比较懒，所以他喜欢把牛拴在木桩上，小Biu有N头牛和N个木桩，农场的总长度为M，每头牛的身长为2*x,N个木桩为位置分别为p[i],现在小Biu想把所有的牛排成一排，并且每只牛都必须栓在木桩上，小Biu一般选择在牛身的中间栓绳子，所以可以认为绳子的位置距离牛头和牛尾的距离都是x。而且一个木桩只能栓一个牛，牛和牛的身体间不能重叠，现在小Biu想知道，如果他想把这N只牛拴在这N个木桩上，需要的所有绳子中的最长的那个绳子长度最小为多少，如果农场不能放下所有的牛，输出-1。

输入

第1行：3个数N X M，中间用空格分隔(1 <= N <= 50000, 1 <= X <= 10^9, 1 <= M <= 10^9)。?
第2 - N + 1行：每行1个数Pi，对应木桩的位置(0 <= Pi <= Pi+1 <= M)，并且给出的数据是有序的。

输出

输出最长绳子的最小值。如果农场排不下所有牛则输出-1。

样例输入?Copy

3 2 16 
1 
3 
14

样例输出?Copy

3

提示

N = 3, X = 2, M = 16。三个木桩的位置为：1 3 14。牛的身长为2*X = 4。你可以将三头牛放在2 6 14（指的是牛身中间所处的位置），这样牛和牛之间既没有重叠，并且所用的最长的绳子最短，长度为3，即第2头牛到第二根木桩的距离。

对于35%的数据，n<=10?
对于70%的数据，n<=10000?
对于100%的数据，n<=50000

分析：

二分答案找最小值

从0-m 范围开始二分

详见代码注释

代码：

#include <iostream>
using namespace std;
int n,x,m;
int ary[50001];
bool check(int mid) //判断 所枚举的答案是否符合题意，彳亍的话返回true，并将mid计入res
{                                             
    int head=0,tail=0;                        
    for(int i=1;i<=n;i++)                     //尽量将牛向前边放，为后面腾出更多空间
    {                                         //ary[i]-mid-x是以柱子为圆心，绳子允许的最
                                              //左边的牛头部位置。
                                              //，或直接采用头部直接连上一头牛的 tail，取两 
                                              //者最大值
                                       //再判断是否超出绳子长度。
         head=max(tail,ary[i]-mid-x);  
        if(head-ary[i]+x>mid)return false;   //如果绳子不够长，返回false
        tail=head+x*2;
        if(tail>m)return false;           //如果后面空间不够，返回false
    }
    return true;
}
int main ()
{
    scanf("%d%d%d",&n,&x,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&ary[i]);
    }
    int left=0,right=m;
    int res=-1;        //设为-1，如果没有可行的答案直接输出-1
    while(left<=right)  //二分答案
    {
        int mid=left+(right-left)/2;
        if(check(mid))
        {                                  // 这个答案行的话比它大的肯定也行，不再判断
            res=mid;   //记录一次行的答案   //  大的数也不是所要找的
            right=mid-1;                   //继续向小的数找
        }                                 
        else                              //这个答案不行的话比它还小的肯定也不行
        {                                    //开始往大了找
            left=mid+1;
        }
    }
    printf("%d\n",res);
    return 0;
}