CF Jumping through segments

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

Problem - D - Codeforces

题目意思是：有k个区间，每一个的左边为l,右边为r。刚开始你的点在0，每一次操作可以把点移动至多k个单位，但要让你的点的pos一直在[l,r]。要求求出最小的k。

二分答案其实我也一直不是很会，emmm。

如果k的值比答案大的话，那么肯定是可以的，所以直接二分就行。

#include<bits/stdc++.h>
using namespace std;
void durant()
{int n;cin>>n;vector<pair<int,int>>v(n);for(auto &[l,r]:v) cin>>l>>r;int left=0,right=1e9+10,ans;while(left<right){int f=0,mid=(left+right)/2;int close=0,far=0;for(auto &[l,r]:v){close=max(l,close-mid);far=min(r,far+mid);if(far<l||close>r){f=1;break;}}if(f){//小了left=mid+1;}else{right=mid;ans=mid;}}cout<<ans<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--)durant();return 0;
}

如果不满足条件则说明k太小，得试试更大的，否则就得试更小的嘛。

这篇关于CF Jumping through segments的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---