2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——F. Fell Walking（在限制最大高度和最小高度之差的前提下，是否连通） · znzryb
## 题目大意
"
F. 徒步旅行
每个测试的时间限制：3.5秒
每个测试的内存限制：1024兆字节
输入：标准输入
输出：标准输出
"
您正在为一位来自荷兰的朋友创建一次峰区山丘之旅。这次旅行将从当地著名的观景点“山1”到世界著名的观景点“山2”。
为了让这位朋友感到宾至如归，您希望尽量减少步行路线中最高和最低山丘之间的高度差。
给定一个地方点和它们之间路径的图，找到这样一个最优平坦路线。
**输入**
- 一行，包含山的数量$n$（$2 \le n \le 5,000$）和连接它们的路径数量$m$（$1 \le m \le 25,000$）。
- 一行，包含$n$个整数$h_1 \ldots h_n$（$0 \le h \le 10^6$），表示从第$1$到第$n$座山的高度（单位：米）。
- $m$行，每行包含两个整数$a$和$b$（$1 \le a, b \le n$），表示山$a$和山$b$之间存在双向路径。
保证山$1$和山$2$之间存在路径（直接或间接）。
## 思路讲解
1. **离散化高度**：
将地图中所有出现过的山丘高度提取出来，从小到大排序，并去重。得到一个有序序列 $H = \{y_1, y_2, \dots, y_k\}$。
1. **双指针（滑动窗口）**：
设置两个指针 `left` 和 `right`，对应高度序列中的索引。
- **固定** **`left`****，移动** **`right`**：尝试寻找满足连通性的最小 `right`。
- 一旦 Hill 1 和 Hill 2 连通，记录当前差值 $H[right] - H[left]$，然后尝试增大 `left`（收缩窗口）看是否依然连通。
- **连通性检查**：可以使用 **BFS**、**DFS** 或者 **并查集 (DSU)**。
1. **复杂度分析**：
- 高度去重后最多有 $N$ 个。
- 外层双指针移动 $O(N)$ 次。
- 每次移动进行一次图遍历 $O(N + M)$。
- 总复杂度约为 $O(N \times (N + M))$。
- 题目给出了 **3.5 秒** 的宽裕时限，对于 $N=5000, M=25000$ 来说，这个复杂度在 C++ 中是可以跑过的。
```cpp
// 下面就是双指针
for (int i=0;i<N;++i) {
bool isb=false;
for (int j=bp;j<N;++j) {
// 判断是否联通
if (bfs(height_idx_ls[i].first,height_idx_ls[j].first)) {
// 一旦联通，就 break
bp=j;
ans=min(ans,abs(height_idx_ls[i].first-height_idx_ls[j].first));
isb=true;
break;
}
}
// 已经无可救药了
if (!isb) {
bp=N+1;
}
}
```
```cpp
void Solve() {
ll N,M;
cin >> N >> M;
vector<pair<ll,ll>> height_idx_ls(N);
vector<ll> H(N+2);
for (int i=1;i<=N;++i) {
cin>>height_idx_ls[i-1].first;
height_idx_ls[i-1].second=i;
H[i]=height_idx_ls[i-1].first;
}
sort(all(height_idx_ls));
vector<vector<ll>> g(N+2);
for (int i=1;i<=M;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> vis(N+2);
int tim=0;
auto bfs=[&](ll low,ll high) {
if (low>H[1] || H[1]>high) {
return false;
}
if (low>H[2] || H[2]>high) {
return false;
}
queue<ll> q;
q.push(1);
++tim;
vis[1]=tim;
while (!q.empty()) {
ll u=q.front();
q.pop();
for (auto v:g[u]) {
if (vis[v]>=tim) continue;
if (low>H[v] || H[v]>high) {
continue;
}
q.push(v);
vis[v]=tim;
}
}
if (vis[2]>=tim) {
return true;
}
return false;
};
ll ans=INF;
ll bp=0;
// 下面就是双指针
for (int i=0;i<N;++i) {
bool isb=false;
for (int j=bp;j<N;++j) {
// 判断是否联通
if (bfs(height_idx_ls[i].first,height_idx_ls[j].first)) {
bp=j;
ans=min(ans,abs(height_idx_ls[i].first-height_idx_ls[j].first));
isb=true;
break;
}
}
// 已经无可救药了
if (!isb) {
bp=N+1;
}
}
cout<<ans<<"\n";
}
```
## AC代码
AC
[https://qoj.ac/submission/2010554](https://qoj.ac/submission/2010554)
::: 源代码
```cpp
/**
* Problem: F. Fell Walking
* Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
* Judge: Codeforces
* URL: https://codeforces.com/gym/106157/problem/F
* Created: 2026-02-06 15:27:15
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct LowHigh {
ll low,high;
};
void Solve() {
ll N,M;
cin >> N >> M;
vector<pair<ll,ll>> height_idx_ls(N);
vector<ll> H(N+2);
for (int i=1;i<=N;++i) {
cin>>height_idx_ls[i-1].first;
height_idx_ls[i-1].second=i;
H[i]=height_idx_ls[i-1].first;
}
sort(all(height_idx_ls));
vector<vector<ll>> g(N+2);
for (int i=1;i<=M;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> vis(N+2);
int tim=0;
auto bfs=[&](ll low,ll high) {
if (low>H[1] || H[1]>high) {
return false;
}
if (low>H[2] || H[2]>high) {
return false;
}
queue<ll> q;
q.push(1);
++tim;
vis[1]=tim;
while (!q.empty()) {
ll u=q.front();
q.pop();
for (auto v:g[u]) {
if (vis[v]>=tim) continue;
if (low>H[v] || H[v]>high) {
continue;
}
q.push(v);
vis[v]=tim;
}
}
if (vis[2]>=tim) {
return true;
}
return false;
};
ll ans=INF;
ll bp=0;
for (int i=0;i<N;++i) {
bool isb=false;
for (int j=bp;j<N;++j) {
if (bfs(height_idx_ls[i].first,height_idx_ls[j].first)) {
bp=j;
ans=min(ans,abs(height_idx_ls[i].first-height_idx_ls[j].first));
isb=true;
break;
}
}
// 已经无可救药了
if (!isb) {
bp=N+1;
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2010554
*/
```
:::
## 心路历程（WA，TLE，MLE……）