P1315 观光公交

题目描述

风景迷人的小城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,000，0 ≤ k ≤ 100 ，0 ≤ Di ≤ 100，0 ≤ T i ≤ 10,000 ；

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

noip2011提高组day2第3题

题目大意：公交车行驶一条路，又上车的下车的还有加速器怎样让乘客下车时间-来等车的时间和最小

题解：

贪心....

边加速边计算答案很麻烦所以我们把不用加速器的答案算出来再减去加速的时间。

关键就是在哪里用加速器...我们要让一个加速器尽可能多的贡献出它的价值，就要让他

造福更多的人。如果这条边上经过的人很多的话，使用加速器会更划算。然后我水了10分QAQ

谢谢公式..car[i]=max(car[i-1],t[i-1])+d[i]. car[i]为汽车到达i点的时间,t[i]为在第i站上车最后一个

人的时间。答案呢就是 ans=sigema(car[ed[i]]-tim[i]) ，发现tim[i]是不变的，即每个人的上车时间

我们让每个人得下车时间尽可能的早就可以了。

加入我们在i--i+1的这条边使用了加速器，那么经过i--i+1的人下车时间都可以-1，如果车行驶到i+1,

发现在i+1上车的最后一个人还没有来，那么在i--i+1上这条边使用加速器只能作用到i+1,也就是说i+1

往后的人他们该什么时候下车就什么时候下车。反之，如果在i+1上车的最后一个人，在车还没来之前

就等着了，那么在i+1上车的人像做了顺风车一样时间也都减少1，我们要这一条这样边，让他造福的人

最多，效力持续最大！注意每次加速之后更新car[]。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,d[1002],tim[10002],st[10003],ed[10003],car[1002],g[1002],t[1002],sum[1002];
int ans,fast,maxnn;
int main(){
    scanf("%d%d%d",&n,&m,&k);//jingdian 乘客 氮气
    for(int i=1;i<n;i++)scanf("%d",&d[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&tim[i],&st[i],&ed[i]);
        t[st[i]]=max(t[st[i]],tim[i]);
        sum[ed[i]]++;
    } 
    for(int i=2;i<=n;i++)sum[i]+=sum[i-1];
    car[1]=t[1];
    for(int i=2;i<=n;i++){car[i]=max(car[i-1],t[i-1])+d[i-1];}
    for(int i=1;i<=m;i++)ans+=(car[ed[i]]-tim[i]);
    while(k--){
        g[n]=g[n-1]=n;maxnn=0;
        for(int i=n-2;i>=1;i--)
        g[i]=car[i+1]<=t[i+1]?i+1:g[i+1];
        for(int i=1;i<n;i++)
        if(sum[g[i]]-sum[i]>maxnn&&d[i]){
            maxnn=sum[g[i]]-sum[i];fast=i;
        }
        ans-=maxnn;d[fast]--;
        for(int i=2;i<=n;i++)car[i]=max(car[i-1],t[i-1])+d[i-1];
    }
    printf("%d
",ans);
    return 0;
}