观光公交车题解

问题分析

题目要求使用有限的加速器来减少所有乘客的总旅行时间。每个加速器可以将某段路程 $D_i$ 减少 $1$ 分钟。

关键思路

1. 时间计算

• $f[i]$：公交车到达第 $i$ 个站点的最早时间
• $tim[i]$：在第 $i$ 个站点需要等待的最晚乘客到达时间
• $cnt[i]$：在第 $i$ 个站点下车的乘客数量
• $sum[i]$：从第 $1$ 到第 $i$ 个站点下车乘客数量的前缀和

2. 贪心策略

代码使用优先队列来维护可以加速的区间，每次选择能够节省最多旅行时间的区间进行加速。

算法步骤

1. 初始化计算

• 计算不使用加速器时的基础旅行时间
• 构建线段树维护每个站点的等待时间信息

2. 加速器分配

• 使用优先队列存储可加速区间，按节省时间排序
• 每次选择最优区间，使用尽可能多的加速器
• 更新线段树和优先队列

3. 最终计算

• 重新计算使用加速器后的总旅行时间

代码核心组件

线段树

• 维护 $f[i] - tim[i]$ 信息
• 支持区间修改和区间查询最小值

优先队列

• 存储可加速区间 $(l, r, val)$
• $val = sum[r] - sum[l-1]$ 表示该区间能节省的旅行时间

复杂度分析

• 时间复杂度：$O((n+m)\log n + k\log n)$
• 空间复杂度：$O(n)$

样例分析

对于样例：

3 3 2
1 4
0 1 3
1 1 2
5 2 3

算法会识别出对 $D_2$ 使用加速器效果最好，使用 $2$ 个加速器将 $D_2$ 从 $4$ 减到 $2$，总旅行时间从 $12$ 减少到 $10$。

执行过程：

1. 初始状态：$D_1 = 1$, $D_2 = 4$
2. 分析发现对 $D_2$ 加速效果最优
3. 使用 $2$ 个加速器：$D_2 = 4 → 2$
4. 总旅行时间：$12 → 10$