洛谷 P1315

修改：

$2026$ 年 $8$ 月 $16$ 日：图片没了，补充上来。

题目大意：

有 $n$ 个站点，和 $m$ 名游客。每一名游客从 $a_i$ 号站点开始旅行，在 $b_i$ 号站点结束旅行，他到达 $a_i$ 站点的时间为 $t_i$。总共有 $k$ 个氮气加速器，每一个加速器可以让观光车从一个站点到另一个站点的时间减一。

解题思路：

这题考查贪心，且信息量较大，要先确定要维护的信息。定义 $last_i$ 表示 $i$ 站点最后一名旅客上车的时间；$sum_i$ 表示在 $i$ 站点下车的人数；$tl_i$ 表示观光车到达 $i$ 站点的时间。对于 $tl$ 数组每一项的值，是可以用上一个站点的信息计算的：观光车到达当前站点的时间等于上一站点观光车到达的时间与上一站点最后一名乘客的到达时间的较大值，加上两站点的行驶时间。那么递推式就是：$tl_i = \max(tl_{i-1},last_{i-1})+d_{i-1}$。接下来考虑如何使用加速器。

如此一来，我们的问题就可转化为如何使用加速器，让分散的区间变少，连续的区间变多。对于两个不连续的区间，比如：观光车到达当前站点的时间为 $12$ 时，而当前站点最后一名游客到达的时间为 $11$ 时，则我们可以通过加速上一个站点，使得观光车到达当前的站点的时间提早，这样既可让当前站点的游客等待时间变少，让前一个区间与当前区间融合，让前一个加速器的影响区间变长，答案更优。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+20;
int n, m, k;
int d[N], t[N], a[N], b[N];
int last[N], tl[N], sum[N];
int f[N];
int main() {
	cin >> n >> m >> k;

	for (int i = 1; i < n; i++) {
		cin >> d[i];
	}

	for (int i = 1; i <= m; i++) {
		cin >> t[i] >> a[i] >> b[i];
		sum[b[i]]++;
		last[a[i]] = max(last[a[i]], t[i]);
	}

	for (int i = 1; i <= n; i++) {
		tl[i] = max(tl[i - 1], last[i - 1]) + d[i - 1];
	}

	while (k--) {
		for (int i = n; i >= 2; i--) {
			f[i - 1] = sum[i];

			if (tl[i] > last[i]) {
				f[i - 1] += f[i];
			}
		}

		int p = 0;

		for (int i = 1; i <= n; i++) {
			if (d[i] && f[p] < f[i]) {
				p = i;
			}
		}

		d[p]--;

		for (int i = 1; i <= n; i++) {
			tl[i] = max(tl[i - 1], last[i - 1]) + d[i - 1];
		}
	}

	int ans = 0;

	for (int i = 1; i <= m; i++) {
		ans += tl[b[i]] - t[i];
	}

	cout << ans;
	return 0;
}