观光公交车问题

题目描述

风景迷人的小城 $Y$ 市，拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多，$Y$ 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。

观光公交车在第 $0$ 分钟出现在 $1$ 号景点，随后依次前往 $2, 3, \dots, n$ 号景点。从第 $i$ 号景点开到第 $i+1$ 号景点需要 $D_i$ 分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有 $m$ 个游客，每位游客需要乘车 $1$ 次从一个景点到达另一个景点，第 $i$ 位游客在 $T_i$ 分钟来到景点 $A_i$，希望乘车去景点 $B_i$ $(A_i<B_i)$。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 $ZZ$ 给公交车安装了 $k$ 个氮气加速器，每使用一个加速器，可以使其中一个 $D_i$ 减 $1$。对于同一个 $D_i$ 可以重复使用加速器，但是必须保证使用后 $D_i\geq0$。

那么 $ZZ$ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

---

输入格式

第 $1$ 行是 $3$ 个整数 $n$, $m$, $k$，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 $2$ 行是 $n-1$ 个整数，每两个整数之间用一个空格隔开，第 $i$ 个数表示从第 $i$ 个景点开往第 $i+1$ 个景点所需要的时间，即 $D_i$。

第 $3$ 行至 $m+2$ 行每行 $3$ 个整数 $T_i$, $A_i$, $B_i$，每两个整数之间用一个空格隔开。第 $i+2$ 行表示第 $i$ 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

---

输出格式

共一行，包含一个整数，表示最小的总旅行时间。

---

样例

输入

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

输出

10

样例解释

对 $D_2$ 使用 $2$ 个加速器，从 $2$ 号景点到 $3$ 号景点时间变为 $2$ 分钟。

公交车的时间线：

• 第 $1$ 分钟从 $1$ 号景点出发
• 第 $2$ 分钟到达 $2$ 号景点
• 第 $5$ 分钟从 $2$ 号景点出发
• 第 $7$ 分钟到达 $3$ 号景点

乘客旅行时间：

• 第 $1$ 个旅客：$7-0 = 7$ 分钟
• 第 $2$ 个旅客：$2-1 = 1$ 分钟
• 第 $3$ 个旅客：$7-5 = 2$ 分钟

总时间：$7+1+2 = 10$ 分钟。

---

数据范围与提示

数据比例	约束条件
$8\%$	$k=0$
$16\%$	$k=1$
$32\%$	$2 \leq n \leq 50$，$m \leq 1000$，$k \leq 20$，$D_i \leq 10$，$T_i \leq 500$
$48\%$	$n \leq 100$，$m \leq 1000$，$k \leq 100$，$T_i \leq 10^4$
$80\%$	$n \leq 1000$，$m \leq 10^4$，$k \leq 10^5$，$D_i \leq 100$，$T_i\leq 10^5$
$100\%$	$1 \leq n,m \leq 10^5$，$0 \leq k \leq 5\times 10^6$，$0 \leq D_i \leq 1000$，$0 \leq T_i \leq 10^6$

---

算法思路

关键观察

1. 公交车运行规则：公交车在站点必须等待所有需要上车的乘客都到达后才能出发
2. 加速器效果：减少路段行驶时间，可能产生连锁效应，让后续站点更早出发
3. 贪心策略：每次选择能减少最多总旅行时间的路段进行加速

核心变量

• arrive[i]：公交车到达站点 $i$ 的最早时间
• latest[i]：站点 $i$ 最晚乘客的到达时间
• off[i]：在站点 $i$ 下车的乘客数量
• sum[i]：从站点 $1$ 到 $i$ 下车乘客数量的前缀和

算法步骤

1. 预处理每个站点的最晚乘客到达时间
2. 计算不使用加速器时的基础旅行时间
3. 使用贪心策略，每次选择能节省最多时间的路段进行加速
4. 重复步骤3直到加速器用完或无法再减少时间

时间复杂度

• 预处理：$O(n + m)$
• 贪心过程：$O(k \cdot n)$（可优化到 $O(k \log n)$）
• 总体：在数据范围内可行