记录编号	193599	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.486 s
提交时间	2015-10-14 21:46:22	内存使用	0.64 MiB

#include<cstdio>
using namespace std;
int n,m,N2,Ans,times[10002],Begin_time[10002],Begin[10002],End[10002],a,b,c,t[10002],d[10002];
int g[10002],sum[10002],ren[10002];
int Max(int x,int y){
    return (x>y)?x:y;
}
void Work_SPJ(){//没有N2优化的，相当于特判；
    for(int i=1;i<=n;++i){
        times[i]=Max(times[i-1],t[i-1])+d[i-1];
    }
    for(int i=1;i<=m;++i)
     for(int j=1;j<=n;++j){
        if(End[i]==j){
            Ans+=times[j]-Begin_time[i]; break;
        }
     }
     printf("%d",Ans);
}
void Work_Right(){
    int Min_number,Best_number,id;
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+ren[i];//前缀和便于求出任意两点间的下车总人数；
    for(int i=2;i<=n;++i) times[i]=Max(times[i-1],t[i-1])+d[i-1];//求出最早的到达时间；
    for(int i=1;i<=m;++i) Ans+=times[End[i]]-Begin_time[i];//不加N2优化的最小值；
    while(N2){
       g[n]=g[n-1]=n;//g[i]表示i能影响的最远距离；
       for(int i=n-2;i>=1;--i)
          if(times[i+1]>t[i+1]) g[i]=g[i+1];
          else g[i]=i+1;
       Min_number=Best_number=0;//找到一个N2能惠利的最多乘客；
       for(int i=1;i<=n;++i){
            Min_number=sum[g[i]]-sum[i];
            if(Min_number>Best_number&&d[i]>0){
                Best_number=Min_number;
                id=i;//记下最优的编号；
            }
       }
       if(!Best_number) break;//不能再优化了，当前肯定是最优解了；
       Ans-=Best_number;
       d[id]--;
       N2--;
       for(int i=2;i<=n;++i) times[i]=Max(times[i-1],t[i-1])+d[i-1];//更新时间；
    }
    printf("%d",Ans);
}
int main(){
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
    scanf("%d%d%d",&n,&m,&N2);
    for(int i=1;i<n;++i) scanf("%d",&d[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c);
        t[b]=Max(t[b],a); End[i]=c; Begin[i]=b; Begin_time[i]=a;
        ren[c]++;
    }
    if(N2==0) Work_SPJ();
    else  Work_Right();
    return 0;
}