这道题很多人都用的模拟（或者暴力），今天我就写一个“标准”的贪心发给大家。（我这段代码差点超时···也差点超内存···）
主要思路：通过贪心求得最小值即可，把加速器用到乘客最多的两个站（或者，如果有许多段路程乘客数都是最多，直接任选K段使用加速器）
代码贴上，大神勿喷
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n,m,k,d[100005],car[100005],g[100005],t[100005],sum[100005],tim[100005],st[100005],ed[100005];
int ans,maxnn,fast;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n-1;i++)
{
scanf("%d",&d[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&tim[i],&st[i],&ed[i]);
t[st[i]]=max(t[st[i]],tim[i]);
sum[ed[i]]++;
}
for(int i=2;i<=n;i++)
{
sum[i]=sum[i]+sum[i-1];
}
car[1]=t[1];
for(int i=2;i<=n;i++)
{
car[i]=max(car[i-1],t[i-1]);
car[i]=car[i]+d[i-1];
}
for(int i=1;i<=m;i++)
{
ans=ans+car[ed[i]]-tim[i];
}
while(k--)
{
g[n]=g[n-1]=n;
maxnn=0;
for(int i=n-2;i>=1;i--)
{
if(car[i+1]<=t[i+1])
{
g[i]=i+1;
}
else
{
g[i]=g[i+1];
}
}
for(int i=1;i<n;i++)
{
if(sum[g[i]]-sum[i]>maxnn && d[i]!=0)
{
maxnn=sum[g[i]]-sum[i];
fast=i;
}
}
ans=ans-maxnn;
d[fast]--;
for(int i=2;i<=n;i++)
{
car[i]=max(car[i-1],t[i-1]);
car[i]=car[i]+d[i-1];
}
}
printf("%d\n",ans);
return 0;
}第一次写博客，有点紧张，大家谅解一下，谢谢！