题目描述

风景迷人的小城Y市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后依次前往2、3、4……n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。
设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai<Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。
一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器，每使用一个加速器，可以使其中一个Di减1。对于同一个Di可以重复使用加速器，但是必须保证使用后Di大于等于0。
那么ZZ该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入描述:

第1行是3个整数n,m,k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1个景点所需要的时间，即Di。
第3行至m+2行每行3个整数Ti,Ai,Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出描述:

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

示例1

输入
3 3 2
1 4
0 1 3
1 1 2
5 2 3
输出
10
说明
对D2使用2个加速器，从2号景点到3号景点时间变为2分钟。
公交车在第1分钟从1号景点出发，第2分钟到达2号景点，第5分钟从2号景点出发，第7分钟到达 3 号景点。
第1个旅客旅行时间7-0=7分钟。
第2个旅客旅行时间2-1=1分钟。
第3个旅客旅行时间7-5=2分钟。
总时间7+1+2=10分钟。

备注

对于10%的数据，k=0；
对于20%的数据，k=1；
对于40%的数据，2≤n≤50，1≤m≤1,000，0≤k≤20，0≤Di≤10，0≤Ti≤500；
对于60%的数据，1≤n≤100，1≤m≤1,000，0≤k≤100，0≤Di≤100，0≤Ti≤10,000；
对于100%的数据，1≤n≤1,000，1≤m≤10,000，0≤k≤100,000，0≤Di≤100，0≤Ti≤100,000。

解答

思路大概想到了 可是代码实现却没想到 所以参考题解了 D2T3的贪心果然有难度

我们考虑在每次用加速器有两种情况

  • 到下一个点还需要等待：以后的时间就不再影响了
  • 到下一个点不需要等待：那么就会影响到后面的时间直到出现情况1（或者到最后一个点）

用sum[i]数组记录到i时的总人数 进行前缀和处理 e[i]为i可以影响到的最远的点

那么即是能影响到的人数

这里需要用到贪心思想 即把影响最大的点用加速器

代码 

#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 10010
int n,m,k,ans;
int need[maxn],tim[maxn],from[maxn],to[maxn],sum[maxn],last[maxn],mintime[maxn],e[maxn];
void fast(int x)
{
    while(x--)//枚举加速器 
    {
        e[n]=e[n-1]=n;//每次都初始化影响点  
        int now,Max=-1;//now为影响最大的点 
        for(int i=n-2;i>=1;i--)//从后面推回去 
        {
            if(mintime[i+1]<=last[i+1]) e[i]=i+1;//如果要等待 最多影响到下一个 
            else e[i]=e[i+1];//如果不用等待 就会影响到后面的 
        }
        for(int i=1;i<n;i++)//枚举边 
        {
            int temp=sum[e[i]]-sum[i];//枚举影响 
            if(temp>Max&&need[i]>0)//找出最大影响和位置 并且时间要大于1 
            {
                Max=temp;
                now=i;
            }
        }
        ans-=Max;//答案减去影响到的人数 
        need[now]--;//加速的时间减去 
        for(int i=2;i<=n;i++) mintime[i]=max(mintime[i-1],last[i-1])+need[i-1];//重新计算每个点的最短时间 
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<n;i++) cin>>need[i];
    for(int i=1;i<=m;i++) 
    {
        cin>>tim[i]>>from[i]>>to[i];
        last[from[i]]=max(last[from[i]],tim[i]);//此点的最迟时间为每个人从此点出发的最小值 
        sum[to[i]]++;//在to[i]下车的人数+1 
    }
    mintime[1]=last[1];//第一个点初始化 
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; //前缀和 
    for(int i=2;i<=n;i++) mintime[i]=max(mintime[i-1],last[i-1])+need[i-1];//计算到达每个点所需要的最短时间 
                                                                           //最后一个人到前一个站点的时间和到这个点的时间取max 
    for(int i=1;i<=m;i++) ans+=mintime[to[i]]-tim[i];//计算没有用加速器的答案 后面再减去用加速器的时间 
    fast(k);//加速辣 
    cout<<ans;
} 



来源：Nanchtiy