【NOIP2011 Day 2】觀光公交

【問題描述】

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

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

【分析】

　　設t[i]表示來到第i個景點的乘客最晚的時間，time[i]表示車到達第i個景點的最小時間。

　　因為每個乘客到達的時間已經固定，所以要使總時間最小，就是使Σtime[b[i]]最小，其中b[i]代表每位乘客的目的地。

　　先考慮不用加速器的情況。可以直接遞推求出答案，time[i] = max(time[i - 1],t[i - 1]) + d[i - 1];

　　接下來再來考慮使用加速器減少的時間。對于每個加速器，我們必須使這個加速器獲得最大的效益，即使盡可能多的乘客旅行時間減一。如果我們在i到i + 1間使用加速器的話，那么到i + 1站的乘客的旅行時間都會減一，但是如果time[i + 1]小于t[i + 1]的話，車就要在i + 1站等到t[i + 1]所有的乘客上車，在i + 1站以后下車的乘客的時間是一樣的，也就是說這個加速器對后面下車的乘客沒有影響。我們可以用遞推求出每個i最遠能影響的車站。

　　g[i] = g[i + 1] ? ?(time[i + 1] > t[i + 1])

　　g[i] = i + 1 (time[i + 1] <= t[i + 1])

　　那么，我們用一個加速器所能減少一個單位時間的乘客就是sum[g[i]] - sum[i]，每次找出使這個最大的i即可。然后把ans減掉，維護time,g

　　這題說白了就是貪心。加速器的使用各不影響。易知這個貪心是正確的。

　　代碼還是比較好寫的。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{int start,arrive,target;
}a[20000];
int n,m,K,ans;
int f[20000],Time[20000],g[20000],dist[20000],sum[20000];
int main()
{scanf("%d %d %d",&n,&m,&K);for (int i = 1;i < n;i ++)scanf("%d",&dist[i]);for (int i = 1;i <= m;i ++){scanf("%d %d %d",&a[i].arrive,&a[i].start,&a[i].target);f[a[i].start] = max(f[a[i].start],a[i].arrive);sum[a[i].target] ++ ;}for (int i = 2;i <= n;i ++)sum[i] += sum[i - 1];Time[1] = 0;for (int i = 2;i <= n;i ++)Time[i] = max(Time[i - 1],f[i - 1]) + dist[i - 1];for (int i = 1;i <= m;i ++)ans += Time[a[i].target] - a[i].arrive;while (K){g[n] = n;g[n - 1] = n;for (int i = n - 2;i ; i -- ){if (Time[i + 1] <= f[i + 1])g[i] = i + 1;else g[i] = g[i + 1];}int Max = 0,j;for (int i = 1;i <= n;i ++)if (sum[g[i]] - sum[i] > Max && dist[i] > 0)Max = sum[g[i]] - sum[i],j = i;if (!Max) break;ans -= Max;dist[j] --;K --;Time[1] = 0;for (int i = 2;i <= n;i ++)Time[i] = max(Time[i - 1],f[i - 1]) + dist[i - 1];}cout << ans;
}

?

?