洛谷1315 观光公交

题意

自己去看吧太长了我懒得总结了

题解

可以发现，对一段路使用了加速器，那么在区间终点下车的乘客旅行时间都会 $-1$ 。所以可以预处理出每个点下车的人数 $q[i]$ 。

预处理出最开始每个点的到达时间 $arr[i]$ 和 每个点最后到达的旅客时间 $last[i]$ 。如果使用加速器后能让下一段路的起点 $i$ 提前开车，即满足 $arr[i]-1<last[i]$ ，那么在下一段路的终点 $i+1$ 下车的乘客时间也会 $-1$ 。依此类推，后面所有满足 $arr[i]-1<last[i]$ 的点都会被影响。

那么就可以暴力枚举区间，算出每个区间的贡献后取贡献最大的区间用加速器，最后计算答案。时间复杂度 $O(n^2k)$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=1005,M=10005;
int n,m,k,t[M],a[M],b[M],d[N],last[N],q[N],arr[N];

signed main()
{
    n=read(); m=read(); k=read();
    for (int i=1;i<n;i++) d[i]=read();
    for (int i=1;i<=m;i++)
    {
        t[i]=read(); a[i]=read(); b[i]=read();
        last[a[i]]=max(last[a[i]],t[i]);
        q[b[i]]++; //下车人数
    }
    for (int i=1,j=0;i<=n;j+=d[i],i++)
    {
        arr[i]=j; //到达时间
        j=max(j,last[i]);
    }
    while (k--)
    {
        int mx=0,mxi;
        for (int i=1;i<n;i++)
        {
            if (!d[i]) continue;
            int cur=0; //选第 i 个区间的贡献
            for (int j=i+1;j<=n;j++)
            {
                cur+=q[j];
                if (arr[j]-1<last[j]) break;
            }
            if (cur>mx) mx=cur,mxi=i; //取最大值
        }
        d[mxi]--; //使用加速器
        for (int j=mxi+1;j<=n && --arr[j]>=last[j];j++); //更新到达时间
    }
    int ans=0;
    for (int i=1;i<=m;i++) ans+=arr[b[i]]-t[i]; //计算答案
    printf("%d",ans);
    return 0;
}