信息学奥赛一本通(C++版)在线评测系统

本网站由成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:307432527,仅供教师加入
初赛题库:提高组 普及组

拥有自我:一本通自由题库
你现在还未登录哦!
用户登录
注册新用户

1868:【11NOIP提高组】观光公交


时间限制: 1000 ms         内存限制: 131072 KB
提交数: 295     通过数: 170

【题目描述】

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

设共有$m$个游客,每位游客需要乘车$1$次从一个景点到达另一个景点,第i位游客在$T_i$分钟来到景点$A_i$,希望乘车前往景点$B_i(A_i<B_i)$。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。

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

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

【输入】

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

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

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

【输出】

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

【输入样例】

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

【输出样例】

10

【提示】

【输入输出样例说明】

对 $D_2$ 使用$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 ≤ D_i ≤ 10,0 ≤ T_i ≤ 500$;

对于 60%的数据,$1 ≤ n ≤ 100,1 ≤ m≤ 1,000,0 ≤ k ≤ 100,0 ≤ D_i ≤ 100,0 ≤ T_i ≤ 10,000$;

对于 100%的数据,$1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000,0 ≤ k ≤ 100,000,0 ≤ D_i ≤ 100,0 ≤ T_i ≤ 100,000$。

提交 统计信息


本题库与《信息学奥赛一本通(C++版)》(科学技术文献出版社)配套,版权及相关事宜请与本书作者联系,本网站不作解答。
本网站属公益、非盈利性质,不涉及与书相关的商业活动,后期可能适当收取费用以支持网站的运行维护。
目前因个人编写水平有限,网站维护、网站安全方面及部分功能的开发尚不成熟,如遇疑问,请通过版主信箱联系。
感谢成都石室中学Wuvin、Qizy、Xehoth三位同学对本网站的支持,特别鸣谢北京师范大学ACM前校队易超、唐巧、洪涛同学。
版主信箱:ybt_mail@126.com