Description
風景迷人的小城 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 該如何安排使用加速器，才能使所有乘客的旅行時間總和最小？

Input
第 1 行是 3 個整數 n, m, k，每兩個整數之間用一個空格隔開。分別表示景點數、乘客數和氮氣加速器個數。

第 2 行是 n-1 個整數，每兩個整數之間用一個空格隔開，第 i 個數表示從第 i 個景點開往第 i+1 個景點所需要的時間，即 Di。

第 3 行至 m+2 行每行 3 個整數 Ti, Ai, Bi，每兩個整數之間用一個空格隔開。第 i+2 行表示第 i 位乘客來到出發景點的時刻，出發的景點編號和到達的景點編號。

Output
共一行，包含一個整數，表示最小的總旅行時間。

Sample Input
3 3 2
1 4
0 1 3
1 1 2
5 2 3

Sample Output
10

Data Constraint

Hint
【輸入輸出樣例說明】

對 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 ≤ Ti ≤ 500；

對于 60%的數據，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；

對于 100%的數據，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，

0 ≤ Ti ≤ 100,000。

.
.
.
.
.
分析
貪心

我們首先記錄下來到每一站下車的人數，然后枚舉每一個加速器，由于每個乘客的旅行時間只與他到達的時間與下車的時間有關，因此，我們在枚舉每一個加速器的時候，只需要把能夠造福最多人的那一段路加速即可，于是我們可以記錄每一段路所造福的人數，我們暫定每個景點的出發時間為需要從該景點上車的最晚到達的乘客，那么到達時間即為上一個景點的出發時間或到達時間更大的一個值加上從上一個景點到該景點所需要的時間。如果某個景點的出發時間小于到達時間，那么說明若在這段旅程中使用加速器，能夠造福到下一個景點下車的人。通過這個，我們就可以貪心了，然后每次貪心完之后都更新到達景點的時間即可。為了方便計算，我在初始化的時候把所有人的到達景點的時間都減去，這樣就不用最后再減了，就可以直接求需要在每個景點下車的人數*到達該景點的時間的和就行了。

.
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int d[1010],num[1010],last[1010],time1[1010],data[1010];int main() {int n,m,k,ans=0;scanf("%d%d%d",&n,&m,&k);for (int i=2;i<=n;i++)scanf("%d",&d[i]);for (int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);ans-=a;num[c]++;last[b]=max(last[b],a);}for (int i=2;i<=n;i++)time1[i]=max(time1[i-1],last[i-1])+d[i];int bz=0;for (int i=1;i<=k;i++){for (int j=n;j>=2;j--){data[j]=num[j];if (last[j]<time1[j]) data[j]+=data[j+1];}int max1=0;for (int j=2;j<=n;j++)if (data[j]>max1&&d[j]>0){max1=data[j];bz=j;}d[bz]--;for (int j=bz;j<=n;j++)time1[j]=max(time1[j-1],last[j-1])+d[j];}for (int i=2;i<=n;i++)ans+=num[i]*time1[i];printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10292781.html

總結

以上是生活随笔為你收集整理的观光公交的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。