有一条从南到北的航线，航线上有N个机场1-n从南到北分布，每天早上飞机从1飞到n，傍晚从n飞到1。有k组乘客，他们数量为M[k]，从S飞到E，飞机上只有C个座位，计算每天飞机最多能拉多少乘客
贪心可以解决这个问题~（我一开始一直在想dp(lll￢ω￢)）
每个站点让所有乘客都上飞机，如果此时超载了，那么就让目的地离当前站点最远的乘客下飞机。可以用优先队列来维护。
emmm这个代码来自 https://blog.csdn.net/severus_qin/article/details/18956647，侵删
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 #include <vector> 7 using namespace std; 8 const int maxn = 10010; 9 struct event{ 10 int t, c; 11 event(){} 12 event(int a, int b) : t(a), c(b){} 13 bool operator < (const event &rhs)const{ 14 return t < rhs.t; 15 } 16 }; 17 vector<event> v1[maxn], v2[maxn]; 18 int k, n, c, num[2][maxn], ans; 19 int work(vector<event> vv[], int k){ 20 priority_queue<event> que; 21 int res = 0, tmp = 0; 22 for (int i = 1; i <= n; i++){ 23 res += num[k][i]; 24 tmp -= num[k][i]; 25 for (int j = 0; j < vv[i].size(); j++){ 26 tmp += vv[i][j].c; 27 que.push(vv[i][j]); 28 } 29 while(tmp > c){ 30 event tt = que.top(); que.pop(); 31 if (tmp - c >= tt.c){ 32 tmp -= tt.c; 33 num[k][tt.t] -= tt.c; 34 }else{ 35 num[k][tt.t] -= (tmp - c); 36 tt.c -= (tmp - c); 37 tmp = c; 38 que.push(tt); 39 } 40 } 41 } 42 return res; 43 } 44 void solve(){ 45 memset(num, 0, sizeof(num)); 46 for (int i = 0; i < maxn; i++){ 47 v1[i].clear(); v2[i].clear(); 48 } 49 for (int i = 0; i < k; i++){ 50 int x, y, z; 51 scanf("%d%d%d", &x, &y, &z); 52 if (x < y){ 53 v1[x].push_back(event(y, z)); 54 num[0][y] += z; 55 }else{ 56 x = n - x + 1; y = n - y + 1; 57 v2[x].push_back(event(y, z)); 58 num[1][y] += z; 59 } 60 } 61 ans = 0; 62 ans += work(v1, 0); ans += work(v2, 1); 63 printf("%d ", ans); 64 return; 65 } 66 int main(){ 67 while(scanf("%d%d%d", &k, &n, &c) == 3) solve(); 68 return 0; 69 }