一个码头中有N艘船和N个木桩，船的长度为2*X，码头的宽度为M，N个木桩的位置（相对码头左岸的位置）会在数据中给出。船和船之间不能重叠，即每艘船的船头不能超过上一艘船的船尾，当然也不能超出码头的两岸。船和木桩之间用绳子连接，并且1个木桩只能栓1条船，绳子的一头拴在木桩上，另一头拴在船的中间。而船中间到木桩的距离，就是所需的绳子的长度。由你根据给出的条件，排列船的位置，使得所用到的最长的绳子最短。输出这个最短的长度，如果码头排不下所有船则输出-1。
例如：N = 3, X = 2, M = 16。三个木桩的位置为：1 3 14。船的长度为2*X = 4。你可以将三艘船放在2 6 14（指的是船中间所处的位置），这样船和船之间既没有重叠，并且所用的最长的绳子最短，长度为3，即第2艘船到第二根木桩的距离。
Input
第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)，并且给出的数据是有序的。
Output
输出最长绳子的最小值。如果码头排不下所有船则输出-1。
Input示例
3 2 16
1
3
14
Output示例
3
看到最小化最长——二分
我们可以先让船首尾相连，然后根据情况后移
首先判断如果船的长度*数量>码头宽度，输出-1
最初设最短距离为0，最长距离为m-1
二分mid,设数组a存储木桩位置
设变量head为这艘船最左端的位置，tail为这艘船最右端的位置
首尾相连，head=tail
1、如果head+x+绳长<=木桩坐标，那么船的中点可以系在木桩的左边或木桩位置
那么head的最优位置为max(head,a[i]-k-x),更新tail
a[i]-k是系绳子的位置，也就是船的中点，再-x是船头
2、否则,船
如果head+x-a[i]>绳长 mid不满足条件
否则，就紧挨着上一条船放，head不变，tail=2*x
3、最后判断最后一条船的船尾是否越界
#include<cstdio>
#include<algorithm>
#define N 50001
using namespace std;
int n,x,m,a[N],ans,tot;
inline int read()
{
int y=;char c=getchar();
while(c<''||c>'') c=getchar();
while(c>=''&&c<='') {y=y*+c-'';c=getchar();}
return y;
}
inline bool check(int k)
{
int head=,tail=;
for(int i=;i<=n;i++)
{
head=tail;
if(head+k+x<=a[i])
{
head=max(head,a[i]-k-x);
tail=head+*x;
}
else
{
if(head+x-a[i]>k) return ;
tail=tail+*x;
}
}
if(tail>m) return ;
return ;
}
int main()
{
n=read();x=read();m=read();
for(int i=;i<=n;i++) a[i]=read();
if(*x*n>m) {printf("-1");return ;}
int l=,r=m-,mid;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) {ans=mid;r=mid-;}
else l=mid+;
}
printf("%d",ans);
}