---
title: "小蓝与数轴"
created: 2025-11-28
tags:
  - 算法
---

# 小蓝与数轴

## 题目 [小蓝与数轴](https://dashoj.com/d/lqbG1/p/4)

![[image-560c8181.png]]

## 思路分析

大概抽象了一下模型

![[image-58793009.png]]

很容易发现是二分写法

但是问题在于怎么check？

初始可以跳到的范围是[-k,k]，和第一个区间取交集，即第一步可以跳到的范围。

然后再将区间前后扩展k距离，继续和下一个区间取交集，如此遍历完每一个区间。

如果遇到交集不存在则说明游戏无法顺利进行下去。

1. 注意n个区间不一定是递增的，可能一会儿在右边，一会儿在左边。
2. check()的写法，最方便的写法是维护每次能走到的区间，然后通过能走到的区间去判断与 $i-th$ 区间是否有重叠。 维护区间(L,R)刚开始的时候区间是(-k,k)，之后每走一步`L=max(L-k,segs[i].l-x)` `R=min(R+k,segs[i].r+k)`

## 代码实现

```cpp
#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;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[小蓝与换装大赛|小蓝与换装大赛]] 🏠 [[00-刷题理模型]] ➡️ [[愤怒的牛|愤怒的牛]]