观光公交

题目

风景迷人的小城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。共一行,包含一个整数,表示最小的总旅行时间。

输入输出样例

输入样例

3 3 2

1 4

0 1 3

1 1 2

5 2 3

输出样例

10

思路

贪心

设t[i]表示来到第i个景点的乘客最晚的时间,time[i]表示车到达第i个景点的最小时间。

因为每个乘客到达的时间已经固定,所以要使总时间最小,就是使Σtime[b[i]]最小,其中b[i]代表每位乘客的目的地。

先考虑不用加速器的情况。可以直接递推求出答案,

$$ time[i] = max(time[i - 1],t[i - 1]) + d[i - 1] $$

接下来再来考虑使用加速器减少的时间。对于每个加速器,我们必须使这个加速器获得最大的效益,即使尽可能多的乘客旅行时间减一。如果我们在i到i + 1间使用加速器的话,那么到i + 1站的乘客的旅行时间都会减一,但是如果time[i + 1]小于t[i + 1]的话,车就要在i + 1站等到t[i + 1]所有的乘客上车,在i + 1站以后下车的乘客的时间是一样的,也就是说这个加速器对后面下车的乘客没有影响。我们可以用递推求出每个i最远能影响的车站。

g[i] = g[i + 1] (time[i + 1] > t[i + 1])

g[i] = i + 1 (time[i + 1] <= t[i + 1])

那么,我们用一个加速器所能减少一个单位时间的乘客就是sum[g[i]] - sum[i],每次找出使这个最大的i即可。然后把ans减掉,维护time,g

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cmath>
#include <cstdio>
#include <iostream>
#define Min(x, y) (x <= y ? x : y)
#define Max(x, y) (x >= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for (flag = false, ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) flag |= ch == '-';
for (x = 0; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
x = flag ? -x : x;
}
int n, m, k, sum[1005 * 2], t[1005 * 2], d[1005 * 2], Time[1005 * 2], g[1005 * 2];
struct node{
int T, A, B;
}peo[10005 * 2];int ans;
inline int work()
{
in(n); in(m); in(k);
F(i, 2, n) in(d[i]);
F(i, 1, m)
{
in(peo[i].T); in(peo[i].A); in(peo[i].B);
t[peo[i].A] = Max(peo[i].T, t[peo[i].A]);
sum[peo[i].B] ++;
}
F(i, 1, n) sum[i] += sum[i-1];
F(i, 2, n) Time[i] = Max(Time[i-1], t[i-1]) + d[i];
F(i, 1, m) ans += Time[peo[i].B] - peo[i].T;
while(k)
{
g[n] = g[n-1] = n;
R(i, n-2, 1)
{
if (Time[i+1] <= t[i+1]) g[i] = i + 1;
else g[i] = g[i + 1];
}
int Max = 0, turn;
F(i, 1, n) if (Max < sum[g[i]] - sum[i] && d[i+1]) Max = sum[g[i]] - sum[i], turn = i + 1;
if (! Max) break;
ans -= Max;
k--;
d[turn] --;
F(i, 2, n) Time[i] = Max(Time[i-1], t[i-1]) + d[i];
}
printf("%d\n", ans);
}
int TAT = work();
int main() {;}