游客 注册 | 登录
中文 | En

2675 - 观光公交

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

某个公交车线路有 N 个站点（但只有1辆车），从第 i 个站点到第 i+1 个站点需要 D[i] 单位时间。现在有 M 名旅客需要搭乘公交车，每位旅客于 T[i] 时间到达 A[i] 车站，并搭乘公交车前往 B[i] 车站。 由于顾客是上帝，所以公交车会等待在该站点上车的所有旅客都上车，然后才继续出发。旅客们都抱怨等待时间（每位旅客到达车站的时间 T[i] 直到旅客到站下车的时间）太长。为了使等待时间缩短，公交车上配备了 K 颗加速器。每使用一个加速器，可以使 D[i] 缩短 1 个单位时间，但前提是D[i]>=0。求在合理使用加速器的情况下，所有旅客等待的总时间的最小值。

题目输入

输入第一行是三个整数 N,M,K 。

第二行含 N-1 个整数，每个整数表示 i 站到 i+1 站所需要的时间 D[i] 。

之后的 M 行每行是一个旅客的到达站点时间 T[i] ，出发站点 A[i] ，目标站点 B[i]。

题目输出

输出所有旅客等待的总时间的最小值。

输入/输出样例

输入格式

3 3 2
1 4
0 1 3
1 1 2
5 2 3

输出格式

10

C++解答

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 1007, M = 10007;
int d[N], Last[N], Come[N], Off[N], People[N], f[N], a[M], b[M], t[M];

int main()
{
	int n, m, k, i, j, p, Res = 0;
	
	cin >> n >> m >> k;
	for (i = 1; i < n; ++i) cin >> d[i];
	for (i = 0; i < m; ++i) {scanf("%d%d%d", &t[i], &a[i], &b[i]); Last[a[i]] = max(Last[a[i]], t[i]);}
	
	for (i = 1; i < n; ++i) Off[i] = max((Come[i] = Off[i - 1] + d[i - 1]), Last[i]);
	Come[n] = Off[n - 1] + d[n - 1];
	for (i = n - 1; i > 0; --i)
		if (Off[i + 1] == Last[i + 1]) f[i] = i + 1;
		else f[i] = f[i + 1];
	for (i = 0; i < m; ++i) ++People[b[i]];
	for (i = 1; i <= n; ++i) People[i] += People[i - 1];
	while (k--)
	{
		p = 0;
		for (i = 1; i <= n; ++i)
			if (d[i] > 0 && People[f[i]] - People[i] > People[f[p]] - People[p]) p = i;
		if (!p) break;
		--d[p];
		for (i = p + 1; i < f[p]; ++i) {--Come[i]; --Off[i];}
		--Come[f[p]];
		for (--i; i >= p; --i)
			if (Off[i + 1] == Last[i + 1]) f[i] = i + 1;
			else f[i] = f[i + 1];
	}
	
	for (i = 0; i < m; ++i) Res += Come[b[i]] - t[i];
	cout << Res << endl;
	
	return 0;
}
请先登陆