風景迷人的小城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該如何安排使用加速器，才能使所有乘客的旅行時間總和最小？
第1行是3個整數n, m, k，每兩個整數之間用一個空格隔開。分別表示景點數、乘客數和氮氣加速器個數。
第2行是n-1個整數，每兩個整數之間用一個空格隔開，第i個數表示從第i個景點開往第i+1個景點所需要的時間，即Di。
第3行至m+2行每行3個整數Ti, Ai, Bi，每兩個整數之間用一個空格隔開。第i+2行表示第i位乘客來到出發景點的時刻，出發的景點編號和到達的景點編號。
共一行，包含一個整數，表示最小的總旅行時間。
3 3 2 1 4 0 1 3 1 1 2 5 2 3樣例輸出1
10限制
1s
提示
樣例說明：
對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。來源
NOIp2011提高組Day2第三題
解析：用完加速器後要使總時間最小，應該是貪心，但是怎麼貪，是一個問題，n個景點，m個乘客，對於每個景點來說，有一個汽車到達的時間arrive[n],還有一個從此景點的出發時間（即乘客的最晚到達時間）latest[n]，我們應該加速的是乘客先到，汽車後到的景點（乘客後到，汽車先到的景點，加速沒有意義啊，乘客不來，老司機也沒有辦法），所以應該找一段區間，滿足兩個要求，一是在這個區間下車的人最多（這樣加速的意義更大，減小即使加速也要在站等乘客的時間），還有一個要求是這段區間滿足每個站點都是汽車後到，乘客先到。滿足這兩個條件的區間即可。
代碼主要步驟
讀數據-->計算bus到i點的時間arrive[i]-->bus從i點出發的最晚時間（即乘客到達i點的最晚時間）latest[i]
-->1--i點有多少乘客在這段區間下車（前綴累加和）-->找同時滿足兩個條件的區間（交集），一個是該區間sum[next[i]-1]-sum[i]
另一個區間是該區間各點均滿足arrive[i]>latest[i](等於不用加速器)（即乘客先到，汽車後到需要加速）
(乘客後到，加速沒有意義)
代碼
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 int n,m,k; 6 int Di[1005]; 7 int t[10005],a[10005],b[10005]; 8 int arrive[1005],latest[1005]; 9 int sum[1005],next[1005]; 10 int minn,sta; 11 int ans; 12 int maxl; 13 int main() 14 { 15 freopen("bus.in","r",stdin); 16 freopen("bus.out","w",stdout); 17 scanf("%d%d%d",&n,&m,&k); 18 for(int i=1;i<=n-1;i++) 19 scanf("%d",&Di[i]); 20 for(int i=1;i<=m;i++) 21 { 22 scanf("%d%d%d",&t[i],&a[i],&b[i]); 23 sum[b[i]]++; 24 if(t[i]>latest[a[i]])latest[a[i]]=t[i]; 25 } 26 //前綴累加和 27 for(int i=2;i<=n;i++) 28 sum[i]+=sum[i-1]; 29 while(1) 30 { 31 //每次更新距離後（用了加速器）都要更新arrive[] 32 arrive[1]=0; 33 for(int i=2;i<=n;i++) 34 arrive[i]=max(arrive[i-1],latest[i-1])+Di[i-1]; 35 //且要更新next[],因為用了加速器後，有些點是不滿足區間條件 36 next[n]=n; 37 for(int i=n-1;i>=1;i--) 38 { 39 //滿足條件區間連續 1（*） 2 3（*） 4（*） 5（*） 6 7（*） 8 40 // 3---next[3]-1 3 6 6 6 6 8 8 8 41 next[i]=next[i+1]; 42 if(arrive[i+1]<=latest[i+1])//第i+1個點不滿足 43 next[i]=i+1; 44 } 45 //貪心需找區間 46 maxl=1; 47 while(!Di[maxl]&&maxl<=n-1) 48 ++maxl; 49 if(maxl==n||k==0)break; 50 //尋找最優區間 51 //i+1--next[i]-1,sum[next[i]]-sum[i]=i+1-- 52 for(int i=maxl+1;i<=n-1;i++) 53 if(Di[i]&&sum[next[maxl]]-sum[maxl]<sum[next[i]]-sum[i]) 54 maxl=i; 55 if(sum[next[maxl]]-sum[maxl]==0)break;//後面已無乘客 56 int dd=100005; 57 for(int i=maxl+1;i<=next[maxl]-1;i++) 58 dd=min(dd,arrive[i]-latest[i]);//最小時間差，乘客先到，汽車後到 59 dd=min(dd,k);//這段區間中使用加速器，所有乘客都受益，所以不存在人數最多相同區間 60 dd=min(dd,Di[maxl]); 61 k-=dd;//區間沒人都受益，受益總和確定 62 Di[maxl]-=dd; 63 } 64 //此時所以bus都比乘客先到達 65 for(int i=1;i<=m;i++) 66 ans+=abs(arrive[b[i]]-t[i]);//防止沒有加速器 ，可能為負 67 cout<<ans<<endl; 68 return 0; 69 }代碼難點
1,前綴和累加.
2,next[n]記錄一段連續區間，滿足要求的區間為 [i+1,next[i]-1].（最好手動寫一遍next[]的數組）
總結
1,貪心條件
2,基礎技法：前綴和累加&&next[i]連續
