思路与算法

模拟最晚登车等待与各站到达时刻，前缀统计下车人数。每次减少收益最大的路段，直到路段耗尽或更早等待屏障变为紧约束为止，再重新计算。

正确性说明

减少一路段一单位只会改善其后至第一个等待屏障（含该站）的到达时刻，收益正是这些站下车人数之和。随着加速，新增等待屏障只会阻断更远收益，不会产生额外收益，边际收益递减；若最优下一单位投给收益较小路段，可交换为当前最大收益路段而不增总时间。批量步长不越过任何中间等待余量且不使路段负值，批内收益恒定，因此等价逐单位贪心。

复杂度

最坏O((k+1)n+m)时间、O(n+m)空间；按稳定收益区间批量减速通常更快，含最晚登车和下车前缀初始化。

易错点

等待屏障所在站的下车乘客也受益，但经过该站继续乘车者会被等待抵消；D可为0，氮气不必全部使用。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> d(n - 1), wait(n), end(n), dest(m), start(m);
    for (int &x : d)
        cin >> x;
    for (int i = 0; i < m; i++) {
        int t, a, b;
        cin >> t >> a >> b;
        wait[a - 1] = max(wait[a - 1], t);
        end[b - 1]++;
        dest[i] = b - 1;
        start[i] = t;
    }
    vector<int> arr(n), stop(n), pref(n + 1);
    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + end[i];
    auto calc = [&]() {
        arr[0] = 0;
        for (int i = 0; i < n - 1; i++)
            arr[i + 1] = max(arr[i], wait[i]) + d[i];
        stop[n - 1] = n - 1;
        for (int j = n - 2; j >= 0; j--)
            stop[j] = arr[j + 1] <= wait[j + 1] ? j + 1 : stop[j + 1];
    };
    calc();
    while (k > 0) {
        int best = -1, gain = 0;
        for (int i = 0; i < n - 1; i++)
            if (d[i] > 0) {
                int g = pref[stop[i] + 1] - pref[i + 1];
                if (g > gain) {
                    gain = g;
                    best = i;
                }
            }
        if (best < 0)
            break;
        int delta = min(k, d[best]);
        for (int j = best + 1; j < stop[best]; j++)
            delta = min(delta, arr[j] - wait[j]);
        d[best] -= delta;
        k -= delta;
        calc();
    }
    long long ans = 0;
    for (int i = 0; i < m; i++)
        ans += arr[dest[i]] - start[i];
    cout << ans << "\n";
}