题目传送门

我是彩笔

二分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;
}