「PA 2020」Samochody dostawcze 题解

算法思路

本题使用哈希映射和碰撞检测的简单方法来解决车辆调度问题。核心观察是两辆车相撞的数学条件可以通过简单的坐标变换来表示。

关键观察

1. 车辆运动模型

• 类型1车辆：从 $(w_i, 0)$ 向北行驶，在时刻 $t$ 的位置为 $(w_i, t - t_i)$
• 类型2车辆：从 $(0, w_i)$ 向东行驶，在时刻 $t$ 的位置为 $(t - t_i, w_i)$

2. 碰撞条件

两辆车在 $(x, y)$ 处相撞的条件是：

• 类型1车辆：$x = w_1$，$y = t - t_1$
• 类型2车辆：$x = t - t_2$，$y = w_2$

联立得：$w_1 = t - t_2$ 且 $w_2 = t - t_1$

消去 $t$ 得到：$w_1 + t_1 = w_2 + t_2$

代码解析

数据存储

map<int, int> mp[2];  // mp[0]存储类型1车辆，mp[1]存储类型2车辆

while (n--) {
    int x, w, t;
    cin >> x >> w >> t;
    mp[x - 1][w - t]++;  // 关键：使用 w-t 作为键值
}

碰撞检测与计数

// 确保所有可能的碰撞键值都存在
for (auto [x, y] : mp[0])
    mp[1][x] += 0;

int ans = 0;
// 对于每个可能的碰撞位置，取两种类型车辆数量的最小值
for (auto [x, y] : mp[1])
    ans += min(y, mp[0][x]);

算法正确性

碰撞条件推导

对于类型1车辆 $(w_1, t_1)$ 和类型2车辆 $(w_2, t_2)$：

• 它们在某个时刻 $t$ 在 $(w_1, w_2)$ 相遇
• 类型1车辆：$w_2 = t - t_1$ ⇒ $t = w_2 + t_1$
• 类型2车辆：$w_1 = t - t_2$ ⇒ $t = w_1 + t_2$
• 因此 $w_1 + t_2 = w_2 + t_1$ ⇒ $w_1 - t_1 = w_2 - t_2$

最少取消数量

对于每个碰撞键值 $k = w - t$：

• 有 $mp[0][k]$ 辆类型1车辆和 $mp[1][k]$ 辆类型2车辆可能相撞
• 最多只能保留 $\min(mp[0][k], mp[1][k])$ 对不相撞的车辆
• 因此需要取消的数量是两者中较小的那个

复杂度分析

• 时间复杂度：$O(n \log n)$（map 操作）
• 空间复杂度：$O(n)$