优先队列专题-白红宇

优先队列专题

阅读量：7136 次

发布时间：2019-06-28

本文共 4118 字，大约阅读时间需要 13 分钟。

1、UVALive 3135 Argus

　　题意：有若干注册信息，每个id每经过一个周期返回一个id信息。求前k个返回信息的id。如果两个信息返回的时间点相同，则小的那个先返回。

　　思路：优先队列简单应用。

1 #include
      
        2 #include
       
         3 #include
         4 #include
         
           5 using namespace std; 6 char s[10]; 7 struct nd 8 { 9     int id;10     int v;11     nd(int ii=0,int vv=0):id(ii),v(vv){ }12     friend bool operator<(const nd&a, const nd&b)13     {14         if (a.v == b.v) return a.id > b.id;15         else return a.v > b.v;16     }17 };18 int main()19 {20     priority_queue
          
           q;21     map
           
            mp;22 while (~scanf("%s", s))23 {24 if (s[0] == '#')break;25 int id, period;26 scanf("%d%d", &id, &period);27 q.push(nd(id, period));28 mp[id] = period;29 }30 int cnt;31 scanf("%d", &cnt);32 while (cnt--)33 {34 nd u = q.top();35 q.pop();36 printf("%d\n", u.id);37 q.push(nd(u.id, u.v + mp[u.id]));38 }39 return 0;40 }

View Code

2、uva 11997 K Smallest Sums

　　题意：给出k个数组，每个数组有k个元素，现在可以从每个数组各选一个数组成和，共有k^k个。求其前k小的数。

　　思路：优先队列+多路归并。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int num[800][800]; 8 struct pos 9 {10     int sum;11     int id;12     pos(int ss=0,int ii=0):sum(ss),id(ii){ }13     friend bool operator<(const pos&a, const pos&b)14     {15         return a.sum > b.sum;16     }17 };18 int main()19 {20     int k;21     while (~scanf("%d", &k))22     {23         for (int i = 0; i < k; i++)24         {25             for (int j = 0; j < k; j++)26             {27                 scanf("%d", &num[i][j]);28             }29             sort(num[i], num[i] + k);30         }31         //多路归并32         for (int i = 1; i < k; i++)33         {34             priority_queue
           
            q;35 for (int j = 0; j < k; j++) q.push(pos(num[0][j] + num[i][0], 0));36 for (int j = 0; j < k; j++)37 {38 pos u = q.top();39 q.pop();40 num[0][j] = u.sum;41 if (u.id + 1 < k) q.push(pos(u.sum - num[i][u.id] + num[i][u.id + 1], u.id + 1));42 }43 }44 for (int i = 0; i < k; i++)45 {46 if (i) printf(" ");47 printf("%d", num[0][i]);48 }49 printf("\n");50 }51 return 0;52 }

View Code

3、uva 11136 Hoax or what

　　题意：每天员工都会向箱子里放他们的业绩单，每天结束的时候，老板从中挑出最高和最低的两份，并奖励高业绩的人数目为业绩之差的奖金。问老板要给出多少奖金。

　　思路：

①两个优先队列。注意一个优先队列的元素可能在另一个优先队列里已经pop。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn = 1000100; 7 int numq1[maxn]; 8 int numq2[maxn]; 9 int main()10 {11     int n;12     while (~scanf("%d", &n))13     {14         if (n == 0) break;15         priority_queue

, greater

>q1;16 priority_queue

, less

>q2;17 memset(numq1, 0, sizeof(numq1));18 memset(numq2, 0, sizeof(numq2));19 20 long long sum = 0;21 for (int i = 0; i < n; i++)22 {23 int m;24 scanf("%d", &m);25 for (int j = 0; j < m; j++)26 {27 int v;28 scanf("%d", &v);29 q1.push(v);30 q2.push(v);31 }32 int u = q1.top(), v = q2.top();33 while (numq2[u])34 { //如果已经在另一个优先队列pop35 numq2[u]--;36 q1.pop();37 u = q1.top();38 }39 while (numq1[v])40 { //如果已经在另一个优先队列pop41 numq1[v]--;42 q2.pop();43 v = q2.top();44 }45 sum += v - u;46 q1.pop(), q2.pop();47 numq1[u]++, numq2[v]++;48 }49 printf("%lld\n", sum);50 }51 return 0;52 }

View Code

②可重集multiset

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main() 5 { 6     int n; 7     while (~scanf("%d", &n) && n) 8     { 9         long long sum = 0;10         multiset
        
         mt;11         for (int i = 0; i < n; i++)12         {13             int k;14             scanf("%d", &k);15             for (int j = 0; j < k; j++)16             {17                 int v;18                 scanf("%d", &v);19                 mt.insert(v);20             }21             sum += *(--mt.end()) - *(mt.begin());22             mt.erase(mt.begin());23             mt.erase(--mt.end());24         }25         printf("%lld\n", sum);26     }27     return 0;28 }

View Code

转载于:https://www.cnblogs.com/ivan-count/p/7427508.html