本文主要是介绍Codeforces Round 913 (Div. 3) D. Jumping Through Segments （二分*1400），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
很容易看出这道题应该二分答案，本题的难点在于对于mid的验证。
找距离肯定是不难，难就难在我们输入的区间并不是按照左右顺序排列的，有的区间可能涵盖住了另一个区间，也就是说在这里我们需要进行的是左右的移动。
那么我们根本无法预知后面的线段在什么位置，所以并不能精准的对每次移动的距离进行一个控制，所以我们要采取向两边进行扩展的方法。
在一开始我们设定左右边界为0，每一次进行扩展的时候，我们就去观察向左扩展k和向右扩展k是否能有一种情况延伸到下一个节点的端点，如果延伸到了就代表着这个节点我们能够移动到。
在这个时候，我们还需要使得左右端点取到线段里面。
那么为什么扩展区域的方法是对的，其实我们的区域代表的是我们在上一次移动之后有可能到达的区域，也就是说在这里并未规定确切的到达的点位，而是使用了一个区域来代表所有可能的点位。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N = 2e5 + 10;
pii a[N];
int n;bool check(int k){int l = 0,r = 0;for(int i = 1;i <= n;i++){l = l - k;r = r + k;if(l > a[i].second || r < a[i].first)return false;l = max(l,a[i].first);r = min(r,a[i].second);}return true;
}void solve(){cin >> n;for(int i = 1;i <= n;i++)cin >> a[i].first >> a[i].second;int l = 0,r = 1e9;while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << l << endl;
}signed main(){int T;cin >> T;while(T--){solve();}return 0;
}
这篇关于Codeforces Round 913 (Div. 3) D. Jumping Through Segments （二分*1400）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
