觀光公交

【問題描述】?

風景迷人的小城 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 大于等于 0。

?那么 ZZ 該如何安排使用加速器，才能使所有乘客的旅行時間總和最小？

?

【輸入】

?輸入文件名為bus.in。

第 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 位乘客來到出發景點的時刻，出發的景點編號和到達的景點編號。

?

【輸出】

?輸出文件名為bus.out。共一行，包含一個整數，表示最小的總旅行時間。

?

【輸入輸出樣例】 ????? ?

bus.in	bus.out?
3 3?2 1 4 0 1 3 1 1 2 5 2 3 ?	10

【輸入輸出樣例說明】

對 D₂ 使用 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。

---

?思路：

一道有意思的貪心~

?

解析代碼

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std ;
const int maxn=1005,maxm=10005;int n,m,ans,k;
int lat[maxn],from[maxn],arr[maxn],down[maxn];struct node{int val,tim,l,r;
};struct cmp{inline bool operator ()(node ax,node bx){return ax.val<bx.val;}
};priority_queue<node,vector<node>,cmp>q;struct Node{int y,t;
}a[maxm];void work(int l,int r){if(l>=r) return;if(!from[l]){                    //不花時間？下一個 work(l+1,r);return;}for(int i=l+1;i<r;i++) if(lat[i]>=arr[i]){         //拆分可減速的分段 
            work(l,i),work(i,r);return;}int minn=from[l],val=down[r];   // minn: l 到 l+1 的距離 ，val: r點下車的總人數 for(int i=1+l;i<r;i++) minn=min(minn,arr[i]-lat[i]),val+=down[i]; //找到最優下車所減時間 from[l]-=minn; 　　//更新 for(int i=1+l;i<r;i++) arr[i]-=minn; //更新 
    q.push((node){val,minn,l,r});  
}int main()
{scanf("%d%d%d",&n,&m,&k);                  // n 站，m 乘客，2 加速 for(int i=1;i<n;i++) scanf("%d",&from[i]); // i -> i+1 的距離 for(int i=1,x;i<=m;i++){                scanf("%d%d%d",&a[i].t,&x,&a[i].y);    // a[i].t 乘客到站時間，從 x 站，到 a[i].ylat[x]=max(a[i].t,lat[x]);             // 從 x 點出發的時間：lat[x]ans-=a[i].t;                           // ans - 起始時間down[a[i].y]++;                        // 終點下車人數
    }for(int i=1;i<n;i++) arr[i+1]=max(arr[i],lat[i])+from[i]; // 更新到站的時間for(int i=2;i<=n;i++) ans+=down[i]*arr[i];                // ans + 到達終點的時間 work(1,n);while(!q.empty() && k)    {node x=q.top();q.pop();ans-=x.val*min(x.tim,k);k-=min(x.tim,k);if(k) work(x.l,x.r); //看能不能再減 
    }printf("%d\n",ans);return 0;
}
/* 
3 3 2 
1 4 
0 1 3 
1 1 2 
5 2 3 
*/  

?