[NOIP 2011] 观光公交

题目描述

风景迷人的小城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该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入输出格式

输入格式：

输入文件名为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,0

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

题解：

好题！想了许久终于有了些结果：

设 arr[i] 为到达i站的时间，last[i]为i站最后一个上车的人的时间

1.如果arr[i]<last[i] 显然是没有必要加速的

2.如果arr[i]<last[i] 那么i前面的道路时间就对后面不再有影响

基于这些结论，分析数据范围：得出O(nk)是极限复杂度了

那么我们就枚举每一个加速器的使用情况：

显然我们是要将加速器用在能减少总时间最多的边上

设num[i]为终点在i的人数，val[i]为i这条路可以减小的最大总时间

那么就转化为求val最大的i：

对于一条边i，它至少产生num[i+1]的贡献.如果arr[i+1]>last[i+1] 那么对val[i+1]能贡献的它也能贡献所以加上val[i+1]

最后每次循环都要更新arr，答案就是 sigma(终点站的arr-出发时间)

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=1005,M=10005;
 9 int n,m,d[N],last[N],num[N],arr[N],val[N];
10 struct node{
11     int r,s;
12 }a[M];
13 void work()
14 {
15     int x,y,z,k;
16     scanf("%d%d%d",&n,&m,&k);
17     for(int i=1;i<n;i++)scanf("%d",&d[i]);
18     for(int i=1;i<=m;i++){
19         scanf("%d%d%d",&x,&y,&z);
20         num[z]++;if(x>last[y])last[y]=x;
21       a[i].r=z;a[i].s=x;
22     }
23     int t=0;
24     for(int i=1;i<=n;i++){
25         arr[i]=t;
26         t=max(t,last[i])+d[i];
27     }
28     int ma;
29     for(int i=1;i<=k;i++){
30         ma=0;
31         for(int j=n-1;j>=1;j--){
32             if(!d[j])val[j]=0;
33             else{
34                 val[j]=num[j+1];
35                 if(arr[j+1]>last[j+1])val[j]+=val[j+1];
36             }
37         }
38         for(int j=1;j<n;j++){
39             if(d[j] && val[j]>val[ma])ma=j;
40         }
41         if(!ma)break;
42         d[ma]--;
43         for(int j=ma+1;j<=n;j++)
44             arr[j]=max(arr[j-1],last[j-1])+d[j-1];
45     }
46     int ans=0;
47     for(int i=1;i<=m;i++)
48         ans+=arr[a[i].r]-a[i].s;
49     printf("%d
",ans);
50 }
51 int main()
52 {
53     work();
54     return 0;
55 }