P1315 观光公交

题面:https://www.luogu.org/problem/P1315

本题的算法是贪心,可以每次讨论在哪一段使用氮气加速器惠及的人最多,然后做k次即可.
这里需要注意的是:统计人数时arrive[i]>=last[i]+1才可以使用
而找到在第k个站台使用后,k后面的站台的arrive都有可能会受到影响,具体条件是arrive[i]>=last[i]就继续枚举.
这里的arrive[i]要先自减再判断,因为第i个站的arrive和last只会影响到第i+1个站,而不会影响其自身受惠及人数.
Code:
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,k,dis[N],from[N],to[N],tot[N],last[N],arrive[N],ans,t;
int main(){
	int x;
    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++){
        scanf("%d%d%d",&from[i],&x,&to[i]);
        last[x]=max(last[x],from[i]);
        tot[to[i]]++;
    }
    for(int i=1;i<=n;i++){
        arrive[i]=t;
        t=max(t,last[i]);
        t+=dis[i];
    }
    while(k--){
        int max_num=0,max_pos;
        for(int i=2;i<=n;i++){
            if(!dis[i-1]){
				continue;
			}
            int tmp_num=0;
            for(int j=i;j<=n;j++){
				tmp_num+=tot[j];
				if(arrive[j]<=last[j]){
					break;
				}
            }
            if(tmp_num>max_num){
                max_num=tmp_num;
                max_pos=i;
            }
        }
        dis[max_pos-1]--;
        for(int i=max_pos;i<=n;i++){
			arrive[i]--;
			if(arrive[i]<last[i]){
				break;
			}
        }
    }
    for(int i=1;i<=m;i++){
        ans+=arrive[to[i]]-from[i];
	}
    printf("%d\n",ans);
    return 0;
}