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