Flying Right POJ

有一条从南到北的航线，航线上有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，侵删

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 #include <vector>

 using namespace std;

 const int maxn = ;

 struct event{

     int t, c;

     event(){}

     event(int a, int b) : t(a), c(b){}

     bool operator < (const event &rhs)const{

         return t < rhs.t;

     }

 };

 vector<event> v1[maxn], v2[maxn];

 int k, n, c, num[][maxn], ans;

 int work(vector<event> vv[], int k){

     priority_queue<event> que;

     int res = , tmp = ;

     for (int i = ; i <= n; i++){

         res += num[k][i];

         tmp -= num[k][i];

         for (int j = ; j < vv[i].size(); j++){

             tmp += vv[i][j].c;

             que.push(vv[i][j]);

         }

         while(tmp > c){

             event tt = que.top(); que.pop();

             if (tmp - c >= tt.c){

                 tmp -= tt.c;

                 num[k][tt.t] -= tt.c;

             }else{

                 num[k][tt.t] -= (tmp - c);

                 tt.c -= (tmp - c);

                 tmp = c;

                 que.push(tt);

             }

         }

     }

     return res;

 }

 void solve(){

     memset(num, , sizeof(num));

     for (int i = ; i < maxn; i++){

         v1[i].clear(); v2[i].clear();

     }

     for (int i = ; i < k; i++){

         int x, y, z;

         scanf("%d%d%d", &x, &y, &z);

         if (x < y){

             v1[x].push_back(event(y, z));

             num[][y] += z;

         }else{

             x = n - x + ; y = n - y + ;

             v2[x].push_back(event(y, z));

             num[][y] += z;

         }

     }

     ans = ;

     ans += work(v1, ); ans += work(v2, );

     printf("%d\n", ans);

     return;

 }

 int main(){

     while(scanf("%d%d%d", &k, &n, &c) == ) solve();

     return ;

 }

巴特西

Flying Right POJ - 3038

最新文章

热门文章