题目链接：https://www.oj.swust.edu.cn/problem/show/1190
思路：
每在一段路上使用一次加速器，就会对某些人或者说某些路段上的人产生影响，目的是使产生的影响最大。
假设在路段x（x路段链接的是x--x+1两个景点）上使用了一次加速器，并且，到达x+1点后，需要等待，那么这次加速只会影响x+1点下车的人。
对以后的点没有影响。因为加速的那段时间被等待了。什么情况下才要等待呢？在不加速的情况下等待或者时间刚好的时候。如果不等待，那么这次在x路
段的加速相当于也在x+1路段上加速了。那么这个影响可以用递推的方式一次性全部求出来。设g[x]表示在x路段上加速会影响的景点。
g[n-]=n;
for(int i=n-;i>;i--)
{
if(ti[i+]>t[i+])//表示车到达i+1点的时间要大于人到齐的时间
g[i]=g[i+];
else
g[i]=i+;
}
求得了可以影响的最远的点，那么就可以影响的总时间就等于在每个被影响的点下车的人数相加，维护前缀和就行，最后要去每次加速影响的最大值就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=;
struct node
{
int arr,st,ed;//到达车站的时间,起点，终点。
}id[maxn*];
int t[maxn];//最晚时间
int ti[maxn];//到达时间
int sum[maxn];//effect
int dis[maxn];//
int g[maxn];
int n,m,k;
void init ()
{
memset(t,,sizeof(t));
memset(sum,,sizeof(sum));
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
init();
for(int i=;i<n;i++)
scanf("%d",&dis[i]);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&id[i].arr,&id[i].st,&id[i].ed);
t[id[i].st]=max(t[id[i].st],id[i].arr);//到大某点的最晚时间
sum[id[i].ed]++;//到达某点的人数
}
for(int i=;i<=n;i++)
sum[i]+=sum[i-];
for(int i=;i<=n;i++)
ti[i]=max(ti[i-],t[i-])+dis[i-];
int ans=;
for(int i=;i<=m;i++)
ans+=ti[id[i].ed]-id[i].arr;
while(k)//
{
g[n-]=n;
for(int i=n-;i>;i--)
{
if(ti[i+]>t[i+])
g[i]=g[i+];
else
g[i]=i+;
}
int pos=,ma=;
for(int i=;i<n;i++)
{
if(dis[i]&&(sum[g[i]]-sum[i])>ma)
{
ma=sum[g[i]]-sum[i];
pos=i;
}
}
if(!ma)
break;
k--;
dis[pos]--;
ans-=ma;
for(int i=;i<=n;i++)
ti[i]=max(ti[i-],t[i-])+dis[i-];
}
printf("%d\n",ans);
}
return ;
}