传送门
题意：
有两个人，初始在不同的位置，他们需要按照顺序到一些点，求最短的最大相隔距离
n ≤ 1 0 5 n\leq 10^5 n≤105

Solution：
看到“最短的最大”，首先考虑二分，深思熟虑之后发现可以二分+dp+数据结构优化，但是这个方法太难写了，通过观察cf上其他人的做法以及机房各位神犇（orz ckw）的思路，发现了一种非常妙的做法：首先二分答案，然后我们考虑倒着往后推：对于每一个点的i所对应的[L,R]表示只考虑i-n这些点，这两个人能完成任务的区间（也可以近似的看成一个人在第i个点时另一个人可以在的区间，因为除了初始状态不在要到达的点上外其他状态一定是有一个人在要到达的点上），那么怎么转移区间到i-1呢？
首先，i=n时，区间显然为[a[i]-二分的答案,a[i]+二分的答案]，如果i-1在当前区间，说明i-1和i的距离小于我们二分的答案，所以我们可以固定在a[i-1]上的点，跳动另一个点，所以说i-1的区间就为[a[i-1]-二分的答案,a[i-1]+二分的答案]。如果i-1不在当前区间，所以我们必须要把在a[i-1]上的点跳到a[i]上，为了保证跳完后符合我们二分的答案，我们需要把[a[i]-二分的答案,a[i]+二分的答案]和[a[i-1]-二分的答案,a[i-1]+二分的答案]取交集。
最后只需要判断s1或s2是不是在最后得到的区间上即可。
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,s1,s2;
int a[100010];
bool pan(int x)
{
	int l=a[n]-x,r=a[n]+x;
	for (int i=n-1;i>=1;i--)
	{
		if (a[i]>=l&&a[i]<=r) l=a[i]-x,r=a[i]+x;
		else
		{
			l=max(l,a[i]-x);
			r=min(r,a[i]+x);
		}	
	}
	return ((s1>=l&&s1<=r)||(s2>=l&&s2<=r));
} 
int main()
{
	scanf("%d%d%d",&n,&s1,&s2);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	if(s1>s2)swap(s1,s2);
	int L=s2-s1,R=1e9;
	//sort(a+1,a+1+n);
	while (L<=R)
	{
		int mid=L+R>>1;
		if (pan(mid))
			R=mid-1;
		else
			L=mid+1;
	}
	printf("%d",L);
}