【每日一题】—— D. Jumping Through Segments（Codeforces Round 913 (Div. 3)）（二分）

本文主要是介绍【每日一题】—— D. Jumping Through Segments（Codeforces Round 913 (Div. 3)）（二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

在这里插入图片描述

题目大意：

波利卡普正在为一款游戏设计一个关卡。关卡由数线上的 $n$ 段组成，其中 $i$ 段从坐标为 $l_i$ 的点开始，到坐标为 $r_i$ 的点结束。
玩家从坐标为 $0$ 的点开始通关。在一次移动中，玩家可以移动到距离不超过 $k$ 的任意一点。在完成 $i$ 次移动后，玩家必须在 $i$ 段内着陆，也就是在坐标 $x$ 处，即 $l_i \le x \le r_i$ 处着陆。这意味着

第一次移动后，他们必须在第一段（从 $l_1$ 到 $r_1$ ）内；
第二次移动后，它们必须在第二个线段内（从 $l_2$ 到 $r_2$ ）；
…
第 $n$ 次移动后，它们必须位于第 $n$ 段（从 $l_n$ 到 $r_n$ ）内。
如果棋手按照上述规则到达了 $n$ （th）段，那么这个关卡就算完成了。经过一番思考，波利卡普意识到 $k$ 的某些值是不可能完成这个关卡的。
波利卡普不希望这个关卡太简单，所以他要求你确定可以完成这个关卡的最小整数 $k$ 。

题目链接：

D. Jumping Through Segments（Codeforces Round 913 (Div. 3)）

二.思路分析

① 二分k，通过check()函数来判断当前的k是否合适
② check() 函数的原理：

从当前点（move_l，move_r）开始寻找到能够到达的两个边界 L 和 R ，L表示最左端，所以是当前点的左端点减去k，即L=move_l-k，同理最右端R为：R=move_r+k
然后用L和R和第n段的数字进行比较，如果==L>r[i]||R<l[i]==就是false，否则更新当前点：move_l=max(L,l[i])，move_r=min(R,r[i])

三.代码展示

//https://codeforces.com/contest/1907/problem/D
//二分
//
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;int l[200020],r[200020];
int n;bool check(int k)
{int move_l=0,move_r=0;for(int i=0;i<n;i++){int L,R;L=move_l-k;R=move_r+k;if(L>r[i]||R<l[i]){return false;}else{move_l=max(L,l[i]);move_r=min(R,r[i]);}}return true;
}void solve()
{cin>>n;for(int i=0;i<n;i++){cin>>l[i]>>r[i];}int left=0,right=1e9,mid;while(left<right){mid=left+right>>1;if(check(mid)){right=mid;}else{left=mid+1;}}cout<<left<<"\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}