优先队列

http://www.cppblog.com/shyli/archive/2007/04/06/21366.html

stl中的优先队列的模板：
#include <queue> 
priority_queue <int> q;（队头为大，top为大）
这是按照从大到小的队列;
priority_queue<int, vector<int>, greater<int> > q;
这是从小到大的优先队列；
#include <queue> 
struct cmp 
{ 
    bool operator ()(const int &i,const int &j)
     {
        return i>j;
    } 
};

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2127

原来这题是优先队列

View Code

 1 #include<stdio.h>
 2 #include<queue>
 3 #include<vector>
 4 using namespace std;
 5 int main()
 6 {
 7     int n,i,j,a,b,s = 0,x;
 8     priority_queue<int, vector<int>, greater<int> > q;
 9     scanf("%d",&n);
10     for(i = 1 ; i <= n ; i++)
11     {
12         scanf("%d",&x);
13         q.push(x);
14     }
15     while(n>=2)
16     {
17         a = q.top();
18         q.pop();
19         b = q.top();
20         q.pop();
21         q.push(a+b);
22         s += a+b;
23         n--;
24     }
25     printf("%d\n",s);
26     return 0;
27 }

http://acm.hdu.edu.cn/showproblem.php?pid=4006

View Code

 1 #include<stdio.h>
 2 #include<queue>   
 3 #include<vector>  
 4 using namespace std;
 5 int q[10001],d;
 6 int main()
 7 {
 8     int i,j,n,k,a;
 9     char c;
10     while(scanf("%d%d",&n,&k)!=EOF)
11     {
12         priority_queue<int, vector<int>, greater<int> > q;
13         d = 0;
14         for(i = 1 ; i <= n ; i++)
15         {
16             scanf("%*c%c",&c);
17             if(c=='I')
18             {
19                 scanf("%d", &a);
20                 q.push(a);
21                 if(q.size()>k)
22                     q.pop();
23             }
24             else
25             if(c=='Q')
26                 printf("%d\n",q.top());
27         }
28     }
29     return 0;
30 }

http://acm.hdu.edu.cn/showproblem.php?pid=4302两个优先队列实现左右优先吃

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<queue>
  4 #include<vector>
  5 #include<stdlib.h>
  6 int k[100005],w[100005];
  7 using namespace std;
  8 int main()
  9 {
 10     int i,j,a,b,t,n,d,f,g,x,y = 0;
 11     char c[30],num[10];
 12     long s;
 13     scanf("%d",&t);
 14     while(t--)
 15     {
 16         y++;
 17         scanf("%d%d%*c",&d,&n);    
 18         b = 0;
 19         s = 0;
 20         priority_queue <int> q1;
 21         priority_queue<int, vector<int>, greater<int> > q2;
 22         for(i = 1 ;i <= n ; i++)
 23         {
 24             gets(c);
 25             f = 0;
 26             g = 0;
 27             int f1 = 0;
 28             for(j = 0; j < strlen(c) ; j++)
 29             {
 30                 if(c[j]==' ')
 31                  f = 1;
 32                 if(f&&c[j]!=' ')
 33                 {
 34                     f1 = 1;
 35                     num[g++] = c[j]; 
 36                 }
 37             }
 38             if(f1)
 39             {
 40                 num[g] = '\0';
 41                 a = atol(num);
 42                 if(a>b)
 43                     q2.push(a);
 44                 else
 45                     q1.push(a);
 46             }
 47             else
 48             {
 49                 if(q1.size()&&q2.size())
 50                 {
 51                     if(b-q1.top()>q2.top()-b)
 52                     {
 53                         x = 1;
 54                         s+=q2.top()-b;
 55                         b = q2.top();
 56                         q2.pop();
 57                     }
 58                     else if(b-q1.top()<q2.top()-b)
 59                     {
 60                         x = 0;
 61                         s+=b-q1.top();
 62                         b = q1.top();
 63                         q1.pop();
 64                     }
 65                     else
 66                     {
 67                         if(x)
 68                         {
 69                             x = 1;
 70                             s+=q2.top()-b;
 71                             b = q2.top();
 72                             q2.pop();
 73                         }
 74                         else
 75                         {
 76                             x = 0;
 77                             s+=b-q1.top();
 78                             b = q1.top();
 79                             q1.pop();
 80                         }
 81                     }
 82                 }
 83                 else if(q1.size())
 84                 {
 85                         x = 0;
 86                         s+=b-q1.top();
 87                         b = q1.top();
 88                         q1.pop();
 89                 }
 90                 else if(q2.size())
 91                 {
 92                     x = 1;
 93                     s+=q2.top()-b;
 94                     b = q2.top();
 95                     q2.pop();
 96                 }
 97             }
 98         }
 99         printf("Case %d: ",y);
100         printf("%ld\n",s);
101     }
102     return 0;
103 }