SB贪心......暴露了我代码能力巨弱的本质。
解：首先我们应该想到DP(但是我想到了贪心......)
然后分析题目本质，每个点有个限制，最早开走时间不得早于最晚上车时间。
然后我们就可以把每个人看做都在那个时间上车。
然后我们发现，对一个地方使用加速，会影响它后面一段区间。
然后就有个暴力·雏形是枚举在某个点用加速，看它能够减少的时间，取最大的那个用。
然后看一眼数据范围，大概是n²，可以过，只要你每次找到收益最大的点是O(n)即可。
然后发现好难写，细节巨多无比......一直觉得这个算法是错的，因为只有一个想法，根本无法转成代码实现。
然后肝了好久，受不了了，去看题解，发现我TM想的是正解，只是不会实现......
代码实现:
固定数组：limit，up，down，sum，分别表示最晚上车时间，上车人数，下车人数，down的前缀和。
变化数组：dis，to，to_lar，now，influ，分别表示所用时间(D)，最远能影响到的位置，这条影响链上最多能承受减去的时间，抵达这里的时间，这里修改会影响的人数。
大部分可变数组都倒序求出，now是正序求出。
然后试一下某hack数据：
#define wwx AK_IOI #include <cstdio>
#include <algorithm> const int N = , INF = 0x7f7f7f7f, M = ; struct Custom {
int t, A, B;
}a[M]; int n, m, k, dis[N], limit[N], to[N], now[N], up[N], down[N], sum[N], influ[N], to_lar[N]; int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = ; i < n; i++) {
scanf("%d", &dis[i]);
}
for(int i = ; i <= m; i++) {
scanf("%d%d%d", &a[i].t, &a[i].A, &a[i].B);
limit[a[i].A] = std::max(limit[a[i].A], a[i].t);
up[a[i].A]++;
down[a[i].B]++;
}
sum[] = down[];
for(int i = ; i <= n; i++) {
limit[i] = std::max(limit[i], limit[i - ]);
sum[i] = sum[i - ] + down[i];
}
// get limit sum up down while(k) {
now[] = ;
for(int i = ; i <= n; i++) {
now[i] = std::max(now[i - ], limit[i - ]) + dis[i - ];
}
int large = -, pos = -;
to[n] = n - ;
to_lar[n] = INF;
for(int i = n - ; i >= ; i--) {
if(now[i + ] > limit[i + ]) {
to[i] = to[i + ];
to_lar[i] = std::min(to_lar[i + ], now[i + ] - limit[i + ]);
//to_lar[i] = std::min(to_lar[i], dis[i]); <- ERROR
}
else {
to[i] = i;
to_lar[i] = INF;
}
influ[i] = sum[to[i] + ] - sum[i];
//printf("influ : %d %d \n", i, influ[i]);
if(influ[i] > large && to_lar[i] && dis[i]) {
large = influ[i];
pos = i;
}
}
if(to_lar[pos] == ) {
break;
}
to_lar[pos] = std::min(to_lar[pos], dis[pos]);
dis[pos] -= std::min(to_lar[pos], k);
k -= std::min(to_lar[pos], k);
//printf("pos = %d to[] = %d lar = %d \n", pos, to[pos], to_lar[pos]);
} now[] = ;
for(int i = ; i <= n; i++) {
now[i] = std::max(now[i - ], limit[i - ]) + dis[i - ];
} int ans = ;
for(int i = ; i <= m; i++) {
ans += now[a[i].B] - a[i].t;
} printf("%d", ans);
return ;
}
AC代码