【1】题解：P1315 [NOIP 2011 提高组] 观光公交【贪心】

ExFish · 2025-11-26 22:19:20 · 题解

练习贪心中。首先你发现一辆车一定要等齐站点内所有人再出发。然后你考虑到加速的限度：不能让车等人。这样就可以预处理出一个站点的人数（s），一个站点最后人什么时候到（w） 这两个信息。然后考虑一段区间的情况。显然预处理出当前 d 下的到站时间 l。然后我们考虑如何使用加速器。我们考虑一些乘客是一定要等的，也就是前面延误了后面就要等，这样的情况可以计算出贡献。考虑计算一个区间加速后能少的总时间 p（也就是 l>w，延误）这样可以简单合并区间，然后求出加速。之后找到最大优化位置直接暴力做就可以了，时间复杂度 \mathcal O(nk)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,d[N],t[N],a[N],b[N];
int l[N],s[N],w[N],p[N],ans;
void utime(){ for(int i=1;i<=n;i++) l[i]=max(l[i-1],w[i-1])+d[i-1]; }
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<n;i++) cin>>d[i];
    for(int i=1;i<=m;i++) cin>>t[i]>>a[i]>>b[i];
    for(int i=1;i<=m;i++)
        s[b[i]]++, w[a[i]]=max(w[a[i]],t[i]);   
    utime();
    for(int j=1;j<=k;j++){
        for(int i=n;i-1;i--){
            p[i-1]=s[i];
            if(l[i]>w[i]) p[i-1]+=p[i];
        }
        int u=0;
        for(int i=1;i<=n;i++)
            if(d[i]&&p[i]>p[u]) u=i;
        d[u]--;
        utime();
    }
    for(int i=1;i<=m;i++) ans+=l[b[i]]-t[i];
    cout<<ans;
    return 0;
}