递推 10pts

算法分析

1.记录每个站点的最迟到达的人的时间$g[i]$

2.递推出车子到达每个站点的时间$f[i]$

3.观察题目要求是求所有的$\sum f[b[i]]-t[i]$,$t[i]$表示达到时间

当$k=0$的时候不需要选择氮气，那么直接计算即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=10010;
int n,m,k;
int t[M],a[M],b[M]; //到达的时间，起点，终点
int d[N],sum[N]; //站点时间,站点i的下车人数
int g[N],f[N],w[N]; //所有人找到i的最大时间,车子到i的时间,i开始使用氮气的收益
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];
        g[a[i]]=max(g[a[i]],t[i]); //最大时间
        sum[b[i]]++; //统计人数
    }
    for(int i=2;i<=n;i++) //计算车子到达时间
    {
        f[i]=max(f[i-1],g[i-1])+d[i-1];
    }
    int res=0;
    for(int i=1;i<=m;i++) //计算所有人的等待时间
    {
        res+=f[b[i]]-t[i];
    }
    cout<<res;
    return 0;
}

O($nk$)贪心+递推 100pts

算法分析

1.记录每个站点的最迟到达的人的时间$g[i]$

2.递推出车子到达每个站点的时间$f[i]$

3.观察题目要求是求所有的$\sum f[b[i]]-t[i]$,$t[i]$表示达到时间

当t[i]固定的时候，我们希望让f[b[i]]尽可能的小,对于第i个站点使用氮气,收益至少是sum[i+1],同时当f[i+1]>g[i+1]时，我们可以继续缩短后面的f[i+1]....，由于需要使用到i+1，所以我们需要倒着计算收益

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=10010;
int n,m,k;
int t[M],a[M],b[M]; //到达的时间，起点，终点
int d[N],sum[N]; //站点时间,站点i的下车人数
int g[N],f[N],w[N]; //所有人找到i的最大时间,车子到i的时间,i开始使用氮气的收益
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];
        g[a[i]]=max(g[a[i]],t[i]); //最大时间
        sum[b[i]]++; //统计人数
    }
    for(int i=2;i<=n;i++) //计算车子到达时间
    {
        f[i]=max(f[i-1],g[i-1])+d[i-1];
    }
    while(k--)
    {
      
        for(int i=n;i>=2;i--) //计算收益
        {
            w[i-1]=sum[i];
            if(f[i]>g[i]) w[i-1]+=w[i];
        }
        int p=0; //找到最大收益
        for(int i=1;i<n;i++)
        {
            if(d[i]&&w[i]>w[p])
            {
                p=i;
            }
        }
        if(!p) break; //没有收益
        d[p]--; //使用氮气
        for(int i=2;i<=n;i++) //更新车子到达时间
        {
            f[i]=max(f[i-1],g[i-1])+d[i-1];
        }
    }
    int res=0;
    for(int i=1;i<=m;i++) //计算所有人的等待时间
    {
        res+=f[b[i]]-t[i];
    }
    cout<<res;
    return 0;
}