题目传送门
我是彩笔
二分trigger：存在一个最小值，使得当大于最小值时一定成立，小于最小值时一定不成立
#include<bits/stdc++.h>
using namespace std;
int n;
int l[200005]={0},r[200005]={0};
int ss(int len)
{
int now=0;
int lp=0,rp=0;//代表第i此行动后能到达的有效区间
for(int i=1;i<=n;i++)
{
if(l[i]>rp)//在前一个边界的右边
{
if(l[i]-rp>len)return 0;//到不了
rp=min(r[i],rp+len);
lp=l[i];
}
else if(r[i]<lp)//在前一个边界的左边
{
if(lp-r[i]>len)return 0;
lp=max(l[i],lp-len);
rp=r[i];
}
else//有交叉
{
rp=min(r[i],rp+len);
lp=max(l[i],lp-len);
}
}
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
int x=-1,y=2e9+2;
while(x<y-1)
{
int mid=x+(y-x)/2;
if(ss(mid))y=mid;
else x=mid;
}
printf("%d\n",y);
}
return 0;
}