随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

poj 3038 Flying Right

题目大意:有一架坐位固定的飞机,每天早上从1号点飞到N号点,晚上从N号点飞回上号点,中途有些点会有人上飞机,在保证不超载的情况下求一天下来,能载的最多乘客数。
这是一道贪心的题,看了一下discuss里面有位大牛说想像自己就是司机,有3种可能
 1.如果有乘客要上车,那么就让他上,收钱!
    2.如果超载了,把距目的地最远的几个乘客踢下去,退钱。
   3.行驶到下一站
根据这个思想,开始以为要在队列头取出目的最远的乘客,还要从队尾取出目的最近的乘客,因为有可能这是有人要下飞机,所以用了一个双端队列来做,在每次有数据加入队列
就排一次序,显然这种方法超时了,最后想了好久,其实不用完全维护在飞机上的那个队列,只要用一个数组来记录在每个站下飞机的人数就可以了,当有人被踢下去时,更新一下
就OK。
自己还是太菜了,在看了别人思路的情况下,还WA+TLE+RE+CE了20几次,把该犯的错都犯了一遍。最后AC之后,把cin 和cout改成scanf 和printf,居然600+MS一下变成了200+MS。。。。

 1#include<iostream>
 2#include<vector>
 3#include<queue>
 4using namespace std;
 5
 6struct node{
 7    int y;
 8    int v;
 9    const bool operator <(const node &b)const{
10        return y<b.y;
11    }

12}
stem;
13int K,N,C;
14vector<node> dd[10005],sd[10005];
15int a[2][10005];
16
17int f(vector<node> tt[],int flag){
18    priority_queue<node> myque;
19    int k=0,ans=0;
20    for(int i=1;i<=N;i++){
21        ans+=a[flag][i];
22        k-=a[flag][i];
23        for(int j=0;j<tt[i].size();j++){
24            k+=tt[i][j].v;
25            stem=tt[i][j];
26            myque.push(stem);
27        }

28        while(k>C){
29            node top=myque.top();
30            myque.pop();
31            if(k-C>=top.v){
32                k-=top.v;
33                a[flag][top.y]-=top.v;
34            }

35            else{
36                a[flag][top.y]-=(k-C);
37                top.v-=k-C;
38                myque.push(top);
39                k=C;
40            }

41        }

42        
43    }

44    return ans;
45}

46    
47int main()
48{
49    scanf("%d%d%d",&K,&N,&C);
50    int u,v,w;
51    for(int i=1;i<=K;i++){
52        scanf("%d%d%d",&u,&v,&w);
53        stem.v=w;
54        if(v>u){
55            stem.y=v;
56            dd[u].push_back(stem);
57            a[0][v]+=w;
58        }

59        else {
60            u=N-u+1;
61            v=N-v+1;
62            stem.y=v;
63            sd[u].push_back(stem);
64            a[1][v]+=w;
65        }

66    }

67    int ans=0;
68    ans+=f(dd,0);
69    ans+=f(sd,1);
70    printf("%d\n",ans);
71    return 0;
72}

73
74

posted on 2010-04-16 19:47 acleast 阅读(693) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理