题解：P14222 [ICPC 2024 Kunming I] 收集硬币

· · 题解

P14222 [ICPC 2024 Kunming I] 收集硬币 题解

题目大意

有 10^9 个格子排成一行，两个机器人以相同的最大速度 v 移动。有 n 枚硬币在第 t_i 秒出现在格子 c_i ，如果此时有机器人在该格子就能收集硬币。求能收集所有硬币的最小速度 v ，如果不可能输出 -1。

思路

我们发现速度 v 具有单调性：如果某个速度可行，那么更大的速度一定也可行。因此可以用二分查找来求最小速度。

对于每个二分的速度 mid，我们需要验证是否存在两个机器人的移动方案能够收集所有硬币。

验证算法

我们维护两个机器人的可能位置范围：

对于每个新的硬币 i：

  1. 计算时间差 d = (t_i - t_p) \times mid，即机器人最大移动距离
  2. 判断两个机器人能否到达当前硬币位置：
    • 参考点机器人能到达：c_p - d \leq c_i \leq c_p + d
    • 另一个机器人能到达：l - d \leq c_i \leq r + d

根据判断结果更新状态：

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;

int n;
struct node {
    int v, t;  // v: 位置坐标, t: 时间
} a[N]; 

// 按时间排序
bool cmp(node x, node y) {
    return x.t < y.t;
}

// 检查给定速度mid是否可行
bool check(int mid) {
    int p = 1;           // 参考点索引，表示最近确定位置的硬币
    int l = 1, r = 1e9;  // 另一个机器人的可能位置区间[l, r]

    for (int i = 2; i <= n; i++) {
        // 计算时间差对应的最大移动距离
        int d = (a[i].t - a[p].t) * mid;

        // 判断两个机器人是否能到达当前硬币位置
        bool x1 = (a[p].v + d >= a[i].v) & (a[p].v - d <= a[i].v);  // 参考点机器人能到达
        bool x2 = (r + d >= a[i].v) & (l - d <= a[i].v);            // 另一个机器人能到达

        // 根据两个机器人的可达性进行状态转移
        if (x1 && x2) {
            // 两个机器人都能到达：取交集更新区间
            l = min(a[p].v - d, l - d);
            r = max(a[p].v + d, r + d);
            p = i;  // 更新参考点为当前点
        } else if (x1) {
            // 只有参考点机器人能到达：扩展另一个机器人的区间
            p = i;
            l = l - d;  // 区间左边界扩展
            r = r + d;  // 区间右边界扩展
        } else if (x2) {
            // 只有另一个机器人能到达：重置区间
            l = a[p].v - d;  // 以参考点为中心重置左边界
            r = a[p].v + d;  // 以参考点为中心重置右边界
            p = i;           // 更新参考点为当前点
        } else {
            // 两个机器人都无法到达当前硬币
            return 0;  // 当前速度不可行
        }

        // 确保区间在有效范围内[1, 10^9]
        l = max(l, 1ll);
        r = min(r, 1000000000ll);
    }
    return 1;  // 所有硬币都能被收集
}

void solve() {
    int ans = -1;
    cin >> n;
    // 读入硬币数据
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].v;
    }
    // 按时间排序硬币
    sort(a + 1, a + n + 1, cmp);

    // 二分查找最小速度
    int l = 0, r = 1e9, mid;
    while (l < r) {
        mid = l + r >> 1;  // 取中间速度
        if (check(mid)) {
            ans = mid;     // 当前速度可行，尝试更小的速度
            r = mid;
        } else {
            l = mid + 1;   // 当前速度不可行，需要更大的速度
        }
    }   
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

这道题的时间复杂度是：O(T (n \log n + n \log 10^9))

3 秒的时限应该是可以过的

注意事项

  1. 排序：硬币必须按时间排序，因为机器人移动依赖于时间顺序
  2. 区间维护：使用 [l, r] 区间表示另一个机器人的可能位置，避免精确跟踪具体位置
  3. 边界处理：每次更新区间后要限制在 [1, 10^9] 范围内
  4. 状态转移：根据两个机器人的可达性采用不同的更新策略，确保至少有一个机器人能到达每个硬币位置

感谢阅读。