codeforces D - Jumping Through Segments

本文主要是介绍codeforces D - Jumping Through Segments，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

二分 $k$ 。
对于当前 $[l, r]$ 移动 $k$ 之后能到达的最大范围 $[l - k, r + k]$ ，如果下一段线段与该范围无重合区间则该 $k$ 过小，如果有重合区间则更新 $[l, r]$ 为 $max(l-k,next_l,min(r+k,next_r)]$ （重合区间）。

Think Twice, Code Once

#include<bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
using namespace std;
typedef unsigned int ull;
typedef pair<int ,int > pii;
int read(void)
{int x=0,f=1;char c=get();while(!is(c)) (f=c==45?-1:1),c=get();while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();return x*f;
}
void write(int x)
{if(x<0) x=-x,put(45);if(x>9) write(x/10);put((x%10)^48);
}
#define writeln(a) write(a),put(10)
#define writesp(a) write(a),put(32)
#define writessp(a) put(32),write(a)
const int N=2e5+10,M=3e4+10,SN=5e3+10,mod=998244353;
int n;
signed main()
{int T=read();while(T--){n=read();vector<pii > ve;int x,y;dfor(i,1,n) x=read(),y=read(),ve.push_back({x,y});int l=0,r=(int)1e9,ans=-1;auto check = [&] (int x){int l=0,r=0;dfor(i,0,n-1){l-=x,r+=x;if(l>ve[i].second||r<ve[i].first) return false;l=max(l,ve[i].first),r=min(r,ve[i].second);}return true;};while(l<=r){int mid=(l+r)>>1;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}ans^-1?(write(ans),put(10)):puts("-1");}return 0;
}