【NOIP 2011 提高组 Day2】观光公交

题目

---

题解

–这道题有点难呢，但主要方法是贪心
对于每个站点，其实只有两种情况
1. 人等车
2. 车等人
这样一分析，就发现使用加速器后，真正有作用的是1站点
而且对于一条如下的道路
–1–1–2–1–
给最前面的道路加速，受益的只有前面两个站点
所以说我们可以每次都搜一遍所有站点，用2站点把整条道路分成很多段，再对影响人数最多的那一段的最前面的那条路使用加速器，就能让每个加速器的作用发挥到最大

但是每次加速后，每个站点的1或2可能有改变，又因为人到站点的时间是不变的，所以要维护车到达站点的时间，可以用以下的递推式
arrive[i]=max(arive[i-1]，lan[i-1])+d[i-1]
arrive[i]：车到 i 站点的时间
lan[i]：i 站点最迟的人来到站点的时间

这样就OK了

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1;

int n,m,k;
int d[1005];
int t[10005],a[10005],b[10005];
int lan[1005],off[1005];
int arrive[1005];
int ans;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<n;i++)
        scanf("%d",&d[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&t[i],&a[i],&b[i]);
        lan[a[i]]=max(lan[a[i]],t[i]);
        off[b[i]]++;
    }
    for(int i=1;i<=n;i++)
        arrive[i]=max(arrive[i-1],lan[i-1])+d[i-1];
    while(k--){
        int sum=0;
        int maxx=0,maxi=0;
        for(int i=n;i>1;i--){
            if(arrive[i]<=lan[i])
                sum=0;
            sum+=off[i];
            if(d[i-1]>0&&sum>maxx){
                maxx=sum;
                maxi=i-1;
            }
        }
        if(!maxi)
            break;
        d[maxi]--;
        for(int i=1;i<=n;i++)
            arrive[i]=max(arrive[i-1],lan[i-1])+d[i-1];     
    }
    for(int i=1;i<=n;i++)
        arrive[i]=max(arrive[i-1],lan[i-1])+d[i-1]; 
    for(int i=1;i<=m;i++)
        ans+=arrive[b[i]]-t[i];
    cout<<ans;
    return 0;
}