Znzryb's Blog
0%

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——F. Fell Walking（在限制最大高度和最小高度之差的前提下，是否连通）

Posted on Edited on

题目大意

"
F. 徒步旅行

每个测试的时间限制：3.5秒

每个测试的内存限制：1024兆字节

输入：标准输入

输出：标准输出
"

您正在为一位来自荷兰的朋友创建一次峰区山丘之旅。这次旅行将从当地著名的观景点“山1”到世界著名的观景点“山2”。

为了让这位朋友感到宾至如归，您希望尽量减少步行路线中最高和最低山丘之间的高度差。

给定一个地方点和它们之间路径的图，找到这样一个最优平坦路线。

输入

  • 一行，包含山的数量nn（2≤n≤5,0002 \le n \le 5,000）和连接它们的路径数量mm（1≤m≤25,0001 \le m \le 25,000）。

  • 一行，包含nn个整数h1…hnh_1 \ldots h_n（0≤h≤1060 \le h \le 10^6），表示从第11到第nn座山的高度（单位：米）。

  • mm行，每行包含两个整数aa和bb（1≤a,b≤n1 \le a, b \le n），表示山aa和山bb之间存在双向路径。

保证山11和山22之间存在路径（直接或间接）。

思路讲解

  1. 离散化高度：
    将地图中所有出现过的山丘高度提取出来，从小到大排序，并去重。得到一个有序序列 H={y1,y2,…,yk}H = \{y_1, y_2, \dots, y_k\}。

  2. 双指针（滑动窗口）：
    设置两个指针 left 和 right，对应高度序列中的索引。

  • 固定 left****，移动 right：尝试寻找满足连通性的最小 right。
  • 一旦 Hill 1 和 Hill 2 连通，记录当前差值 H[right]−H[left]H[right] - H[left]，然后尝试增大 left（收缩窗口）看是否依然连通。
  • 连通性检查：可以使用 BFS、DFS 或者 并查集 (DSU)。
  1. 复杂度分析：
  • 高度去重后最多有 NN 个。
  • 外层双指针移动 O(N)O(N) 次。
  • 每次移动进行一次图遍历 O(N+M)O(N + M)。
  • 总复杂度约为 O(N×(N+M))O(N \times (N + M))。
  • 题目给出了 3.5 秒 的宽裕时限，对于 N=5000,M=25000N=5000, M=25000 来说，这个复杂度在 C++ 中是可以跑过的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 下面就是双指针
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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

心路历程（WA，TLE，MLE……）