D. Jumping Through Segments

1、首先，假设我们已知一个k，若其符合题意，那么

第一次移动时可达区间为[-k,k]，我们只需判断这个区间和[L1,R1]是否有交区间。然后我们取出这个交区间【left，right】。

接下每次移动，我们都在上一次得到的区间基础上得到新的可移动区间【left-k，right+k】，之后再和【Li，Ri】取交区间。

如果其中有一次交区间为空，那么该k不符合题意，反之，则符合。

2、接下来，通过二分法取k，并执行1步骤判断是否符合，最终可以得到最小的k值。

主要代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pos;
bool process(int mid,vector<Pos> &a,int n){
    int l=0,r=0;
    for (int i=0;i<n;i++){
        l-=mid;r+=mid;  //可移动区间的左右边界 
        if (r<(a[i].first)) return false;  //右边界小于Ri时不符合 
        else if (l>(a[i].second)) return false;//左边界大于Li时不符合 
        else{l=max(l,a[i].first);r=min(r,a[i].second);}  //取交区间 
    }
    return true;
}
int main(){
    int t;
    cin>>t;
    while (t--){
        int n,l,r,max=0;
        cin>>n;
        vector<Pos> a;  //存储每一段区间 
        for (int i=0;i<n;i++){
            cin>>l>>r;
            a.push_back(Pos(l,r));
            if (r>max) max=r;  //找到二分法的最大值 
        }
        int left=0,mid;
        while (left<=max){  //二分查找 
            mid=left+((max-left)>>1);
            if (process(mid,a,n)) max=mid-1;  //判断是否符合题意 
            else left=mid+1;
        }
        printf("%d\n",max+1);
    }
    return 0;
}