题目描述

风景迷人的小城 Y 市，拥有 n 个美丽的景点。

由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。

观光公交车在第 0 分钟出现在 1 号景点，随后依次前往 2、3、4……n 号景点。

从第 i 号景点开到第 i+1 号景点需要 $D_i$ 分钟。 

任意时刻，公交车只能往前开，或在景点处等待。 

设共有 m 个游客，每位游客需要乘车 1 次从一个景点到达另一个景点，第 i 位游客在 Ti 分钟来到景点 Ai，希望乘车前往景点 $B_i$（$A_i$<$B_i$）。

为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。 

假设乘客上下车不需要时间。 

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。

因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。

于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器，每使用一个加速器，可以使其中一个 $D_i$ 减 1。

对于同一个 $D_i$ 可以重复使用加速器，但是必须保证使用后 Di 大于等于 0。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入格式

第 1 行是 3 个整数 n, m, k，每两个整数之间用一个空格隔开，分别表示景点数、乘客数和氮气加速器个数。 

第 2 行是 n-1 个整数，每两个整数之间用一个空格隔开，第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间，即 $D_i$。 

第 3 行至 m+2 行每行 3 个整数 $T_i$, $A_i$, $B_i$，每两个整数之间用一个空格隔开,第 i+2 行表示第 i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出格式

共一行，包含一个整数，表示最小的总旅行时间。

样例

输入样例
3 3 2
1 4
0 1 3
1 1 2
5 2 3

输出样例
10

算法1

(贪心) $O(nk)$

首先阅读一下这个题目，非常的难懂，简化一下题面就是，现在有一辆车，在公路上走，会有一些人要上车，比较厉害的是这些人和超时空步兵一样可以瞬间上车和下车。而且如果人没有到齐，车是不会走的，要等所有人到齐才会走。司机拥有着k次氮气加速。求最少时间。

看完题面，如果没有氮气加速的话就是一个简单的小模拟，所以重点就是在怎么去安排氮气加速的位置。

现在再思考一下怎么让氮气加速影响最大？

首先还需要明白一下，氮气加速可以影响一个区间而不一定是两个景点之间的距离。

比如上图的红色区间。
因为如果所有的乘客到达之后，车是可以不停的，这就运用到了前面说的那个性质，这些乘客有超时空兵一样的技能。所以，现在根据这个性质就可以先判断出氮气加速用在这个点上可以影响的最远距离，然后可以预处理一下每个站点有多少人的前缀和，然后根据判断的最远距离和前缀和就可以算出在这个点使用氮气加速可以影响的最大人数。然后再找到最大影响人数并且距离不为0的点使用氮气加速，再更新一下时间和距离，再次找到可以影响最大的人数，进行k次，因为一共有k个氮气加速。

首先不能做一遍然后找到k个最大的进行加速，因为每加速一次就会改变时间和距离，需要重新求。

C++ 代码

#include<iostream>
using namespace std;
struct hf
{
    int dao,kai,jie;
}a[20000];
int dist[20000],f[20000],sum[20000],t[20000],ans=0,g[20000];
int main()
{
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<n;i++)
    cin>>dist[i];
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].dao>>a[i].kai>>a[i].jie;
        f[a[i].kai]=max(f[a[i].kai],a[i].dao);
        sum[a[i].jie]++;
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]+=sum[i-1];
    }
    t[1]=0;
    for(int i=2;i<=n;i++)
    t[i]=max(f[i-1],t[i-1])+dist[i-1];
    for(int i=1;i<=m;i++)
    ans+=t[a[i].jie]-a[i].dao;
    while(p)
    {
        g[n]=n;
        g[n-1]=n;
        for(int i=n-2;i;i--)
        {
            if(t[i+1]<=f[i+1])
            g[i]=i+1;
            else
            g[i]=g[i+1];
        }
        int maxx=0,j;
        for(int i=1;i<=n;i++)
        if(sum[g[i]]-sum[i]>maxx&&dist[i]>0)
        maxx=sum[g[i]]-sum[i],j=i;
        if(!maxx)
        break;
        ans-=maxx;
        dist[j]--;
        p--;
        for(int i=2;i<=n;i++)
        t[i]=max(f[i-1],t[i-1])+dist[i-1];
    }
    cout<<ans;
}