hdu 4302 优先队列

进一步学习了优先队列的用法

题意：一只小动物在直线上走，起始位置为零，之后会出现食物，动物要去距离自己最短的食物那，若两边的食物距离相等，则选择之前走的方向的食物

0 x，代表x的位置出现了食物，1代表去吃一个食物

 1 #include<stdio.h>
 2 #include<queue>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 struct cmp
 7 {
 8     bool operator()(int x,int y)
 9     {
10         return x>y;
11     }
12 };
13 priority_queue<int,vector<int>,cmp>q;
14 priority_queue<int>q2;
15 int main()
16 {
17     //freopen("in.txt","r",stdin);
18     //freopen("out.txt","w",stdout);
19     int T;
20     int L,n;
21     int A,B;
22     int iCase=0;
23     scanf("%d",&T);
24     while(T--)
25     {
26         iCase++;
27         scanf("%d%d",&L,&n);
28         while(!q.empty())q.pop();
29         while(!q2.empty())q2.pop();
30         int x=0;
31         int ans=0;
32         int t=1;
33         while(n--)
34         {
35             scanf("%d",&A);
36             if(A==0)
37             {
38                 scanf("%d",&B);
39                 if(B>=x)q.push(B);  //记录右边的点
40                 else q2.push(B);    //记录左边的点
41             }
42             else
43             {
44                 if(!q.empty()&&!q2.empty())
45                 {
46                     int temp1=q.top();
47                     int temp2=q2.top();
48                     if(temp1-x<x-temp2)
49                     {
50                         t=1;
51                         ans+=q.top()-x;
52                         x=q.top();
53                         q.pop();
54                     }
55                     else if(temp1-x>x-temp2)
56                     {
57                         t=-1;
58                         ans+=x-q2.top();
59                         x=q2.top();
60                         q2.pop();
61                     }
62                     else if(t==1)
63                     {
64                         ans+=q.top()-x;
65                         x=q.top();
66                         q.pop();
67                     }
68                     else
69                     {
70                         ans+=x-q2.top();
71                         x=q2.top();
72                         q2.pop();
73                     }
74                 }
75                 else if(!q.empty())
76                 {
77                     t=1;
78                     ans+=q.top()-x;
79                     x=q.top();
80                     q.pop();
81                 }
82                 else if(!q2.empty())
83                 {
84                     t=-1;
85                     ans+=x-q2.top();
86                     x=q2.top();
87                     q2.pop();
88                 }
89             }
90 
91         }
92         printf("Case %d: %d
",iCase,ans);
93     }
94     return 0;
95 }

hdu 4302 优先队列

相关推荐