算法知识点: 贪心，递推

复杂度：

解题思路：

这道题目的信息较多，我们先将其整理一下。

首先预处理出每个站台的发车时间，即最后一个到达站台i的时间。然后预处理出从每个站台下车的人数。

接下来求出车到达每个站台的时间，那么每个乘客的旅行时间就是，其中是乘客的终点站，是乘客到达起点的时间。

然后考虑每个氮气加速器该用在哪一段，这里使用贪心策略：每次选择当前节约时间最多的一段。（正确性仍未得证）

节约时间取决于能影响多少位乘客，当我们将某一段的行驶时间减一之后，如果下一个车站的，则车从下一个车站发车的时间也会早一个单位时间，依次类推，每次加速之后，可以影响一段连续的区间。

每次选择节约时间最多的一段来加速即可。

时间复杂度分析:

C++ 代码： 

#include <iostream>
#include <algorithm>
using namespace std; const int N = 1010,
    M = 10010;
 
int n, m, k;
int d[N];
int t[M], a[M], b[M];
int tm[N], last[N];
int sum[N];
int reduce[N];
 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i < n; i++) scanf("%d", &d[i]);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &t[i], &a[i], &b[i]);
        last[a[i]] = max(last[a[i]], t[i]);
        sum[b[i]]++;
    }
 
    for (int i = 1; i <= n; i++) tm[i] = max(tm[i - 1], last[i - 1]) + d[i - 1];
 
    while (k--)
    {
        for (int i = n; i >= 2; i--)
            if (!d[i - 1]) reduce[i - 1] = 0;
            else
            {
                reduce[i - 1] = sum[i];
                if (tm[i] > last[i]) reduce[i - 1] += reduce[i];
            }
 
        int p = 0;
        for (int i = 1; i < n; i++)
            if (reduce[p] < reduce[i])
                p = i;
 
        if (!p) break;
        d[p]--;
        for (int i = p + 1; i <= n; i++) tm[i] = max(tm[i - 1], last[i - 1]) + d[i - 1];
    }
 
    int res = 0;
    for (int i = 0; i < m; i++) res += tm[b[i]] - t[i];
 
    printf("%d\n", res);
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ