小蓝与数轴
题目 小蓝与数轴
思路分析
大概抽象了一下模型
很容易发现是二分写法
但是问题在于怎么check？
初始可以跳到的范围是[-k,k]，和第一个区间取交集，即第一步可以跳到的范围。
然后再将区间前后扩展k距离，继续和下一个区间取交集，如此遍历完每一个区间。
如果遇到交集不存在则说明游戏无法顺利进行下去。
- 注意n个区间不一定是递增的，可能一会儿在右边，一会儿在左边。
- check()的写法，最方便的写法是维护每次能走到的区间，然后通过能走到的区间去判断与 \(i-th\) 区间是否有重叠。 维护区间(L,R)刚开始的时候区间是(-k,k)，之后每走一步
L=max(L-k,segs[i].l-x)R=min(R+k,segs[i].r+k)
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef pair<int,int> PII;
vector<PII> segs;
int n;
// 检查是否能用 k 作为最大跳跃距离覆盖所有区间
bool check(int k){
int curL = -k, curR = k; // 当前可以到达的范围的左右端点
for(int i = 0; i < n; i++){
if(segs[i].first>curR || segs[i].second<curL) // 如果当前区间不在可达范围内
return false;
// 更新当前可达范围为区间与当前范围的交集，并考虑跳跃距离
curL = max(segs[i].first, curL) - k;
curR = min(segs[i].second, curR) + k;
}
return true;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
int maxR=0;
for(int i=0;i<n;i++){
int l,r;cin>>l>>r;
maxR=max(maxR,r);
segs.push_back({l,r});
}
int l=0,r=maxR+1;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}
💬 评论