P1315 观光公交

    • 1.4K通过
    • 3.8K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 贪心 递推 NOIp提高组 2011 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    感谢@Transhumanist 提供的一组Hack数据

    题目描述

    风景迷人的小城 $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 \ge 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$ 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3 3 2
    1 4
    0 1 3
    1 1 2
    5 2 3
    输出样例#1: 复制
    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$ 。

    noip2011提高组day2第3题

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。