noip 2011观光公交

- 95通过
- 244提交
题目提供者该用户不存在
标签贪心递推2011NOIp提高组
难度提高+/省选-

题目描述

风景迷人的小城Y 市，拥有n 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点，随后依次前往 2、3 、4 ……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻，公交车只能往前开，或在景点处等待。

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

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

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

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了 k 个氮气加速器，每使用一个加速器，可以使其中一个 Di 减1 。对于同一个Di 可以重复使用加速器，但是必须保证使用后Di 大于等于0 。

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

输入输出格式

输入格式：

输入文件名为bus.in。

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

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

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

输出格式：

输出文件名为bus.out。共一行，包含一个整数，表示最小的总旅行时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

【输入输出样例说明】

对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 ≤ T i ≤ 500；

对于60% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100 ，0 ≤ Di ≤ 100，0 ≤ T i ≤ 10,000 ；

对于100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000 ，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100 ，0 ≤ T i ≤ 100,000。

noip2011提高组day2第3题

分析：如果不使用加速器，那么总旅行时间是一定的，为了使总旅行时间最少，那么减少的旅行时间一定要最多，一个加速器一次只能使一个d-1,怎么样才能减的更多呢？当然是人多的时候，于是想到贪心策略：在人多的时候用加速器，但是其它的因素比较多，不好证明其正确性，而且用完一个加速器后到达的时间都要减小，既然不能总体分析，那么就一个一个的分析.首先需要计算出每个点的到站人数，通过这个可以计算出车上的人数,那么一个加速器能够影响到多少人呢？（使多少人的旅行时间减少）如果车i车站等人，那么i车站到达的人就不能被影响到，除非人等车.有一些细节需要注意：1.每次处理完一个加速器，就要更新一次观光车从每个景点出发的时间. 2.一定要用完加速器(废话),那么问题就解决了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 20010;

struct node
{
    int bg,arr,end;
}a[maxn];

int n,m,k,ans,sum[maxn],d[maxn],yingxiang[maxn],t[maxn],f[maxn],maxi,maxx;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i < n; i++)
    scanf("%d",&d[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&a[i].arr,&a[i].bg,&a[i].end);
        f[a[i].bg] = max(f[a[i].bg],a[i].arr);
        sum[a[i].end]++;
    }
    for (int i = 2; i <= n; i++)
    sum[i] += sum[i-1];
    t[1] = 0;
    for (int i = 2; i <= n; i++)
    t[i] = max(t[i-1],f[i-1])+d[i-1];
    for (int i = 1; i <= m; i++)
    ans += t[a[i].end] - a[i].arr;
    while (k > 0)
    {
        yingxiang[n] = n;
        yingxiang[n-1] = n; 
        for (int i = n - 2; i; i--)
        if (t[i+1] <= f[i+1])//车等人，不会影响到后面的人
        yingxiang[i] = i + 1;
        else
        yingxiang[i] = yingxiang[i + 1];
         maxx = 0;
         for (int i = 1; i <= n; i++)
         if (sum[yingxiang[i]] - sum[i] > maxx && d[i] > 0)
         maxx = sum[yingxiang[i]] - sum[i],maxi = i;
         if (!maxx)
         break;
         ans -= maxx;
         d[maxi]--;
         k--;
         t[1] = 0;
         for (int i = 2; i <= n; i++)
         t[i] = max(t[i-1],f[i-1]) + d[i-1]; 
    }
    printf("%d",ans);
    
    return 0;
}