【刷题】【贪心】观光公交

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,K;
const int N=100003;
int dis[N],out[N],peo[N],bus[N];//dis[i]表示到下一站的时间，中间会修改，peo表示每个站人到的最后时间，不修改，bus表示车到的时间，被dis影响 
int ans;

int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<n;i++) scanf("%d",&dis[i]);
    for(int i=1;i<=m;i++)
    {
        int tm,st,ed;
        scanf("%d%d%d",&tm,&st,&ed);
        ans-=tm,peo[st]=max(tm,peo[st] ),out[ed]++;
    }
    //work
    int inf[N];//如果在i-i+1站中间，用装备，会对后面的人造成的影响 
    while(K--)
    {
        for(int i=2;i<=n;i++)
            bus[i]=max(peo[i-1],bus[i-1])+dis[i-1];
        
        for(int i=n-1;i>0;i--)
            if(dis[i]) 
            {
                inf[i]=out[i+1]; //i+1站下车的人 
                if(bus[i+1] > peo[i+1] )//i+1后面的人。如果后面是车到的慢，那么我用还能为后面的人做贡献 
                    inf[i]+=inf[i+1];
            }
            else inf[i]=0;
        
        int mx_inf=0,pos=0;
        for(int i=1;i<n;i++)
            if(inf[i] > mx_inf )
                mx_inf=inf[i],pos=i;
        
        if(!pos) break;
        dis[pos]--;
    }
    //output
    for(int i=2;i<=n;i++ )
    {    
        bus[i]=max(peo[i-1],bus[i-1])+dis[i-1] ;
        ans+=out[i]*bus[i] ;
    }
    printf("%d\n",ans);
    return 0;
}