题解：P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku

Warren1022 · 2025-10-28 17:05:17 · 题解

P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku题解

题目传送门

算法设计

• 核心优化思路 将 “逐秒移动” 转化为 “批量计算单次连续移动的距离”：
  1. 每次移动前，确定下一个触发反弹的目标（最近的未处理 # 或边界）
  2. 直接计算当前位置到目标的距离，累加为总时间，跳过中间逐秒计算
  3. 处理目标后更新方向和未处理 # 列表，重复至所有 # 处理完毕
• 数据结构与工具
• 二分查找：用函数"lower_bound" 快速定位 “当前方向上最近的未处理 #”，时间复杂度 (O(\log M)（M 为 # 数量）

  代码实现

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, a;
    string s;
    cin >> n >> a >> s;

    vector<int> h;
    for (int i = 0; i < n; ++i)
        if (s[i] == '#') h.push_back(i + 1);  // 转为1-based位置

    int m = h.size();
    sort(h.begin(), h.end());
    long long t = 0;
    int p = a, d = 1, l = 0, r = n + 1;

    while (m) {
        if (d == 1) {  // 向右移动
            auto it = lower_bound(h.begin(), h.end(), p);
            int nh = (it != h.end()) ? *it : r + 1;
            int np = min(nh, r);

            t += np - p;
            p = np;

            if (p == r) d = -1;
            else { h.erase(it); m--; d = -1; }
        } else {  // 向左移动
            auto it = lower_bound(h.begin(), h.end(), p);
            int nh = (it != h.begin()) ? *prev(it) : l - 1;
            int np = max(nh, l);

            t += p - np;
            p = np;

            if (p == l) d = 1;
            else { h.erase(prev(it)); m--; d = 1; }
        }
    }

    cout << t << '\n';
    return 0;
}

复杂度分析

1. 时间复杂度：O(M \log M)
   • 收集 # 位置：O(N)
   • 排序 # 列表：O(M \log M)
   • 处理每个 #：每次二分查找 O(\log M)
   • vector$ $erase$ 操作 $O(1)$，因为每个 **#** 仅删除一次），总 $O(M \log M)
2. 空间复杂度：(O(M)，仅存储 # 位置的 vector