priority_queue：优先队列-白红宇

priority_queue：优先队列

阅读量：340 次

发布时间：2019-03-04

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

优先队列的使用是一种高效的数据结构，用于管理和检索最大或最小的元素。在本文中，我们将学习如何使用优先队列来解决两个具体的问题。第一个问题涉及游戏规则，第二个问题涉及寻找大富翁。

问题一：游戏规则

在这个游戏中，Xiao Ming和Xiao Bao轮流进行操作。Xiao Ming可以选择写下一个数字或询问Xiao Bao关于“kth great number”的问题。我们的任务是根据输入的指令，处理这些操作，并在询问时输出相应的结果。

输入格式

每个测试用例的第一行给出两个整数n和k。接下来有n行，每行要么是“I”加上数字，要么是“Q”。当遇到“I”时，将数字添加到优先队列中，并且如果队列的大小超过k，就弹出队列的最小元素。对于“Q”操作，则需要输出当前队列的第k大的元素。

输出格式

对于每个询问操作，输出当前队列的第k大的元素。

示例输入

8 3 I 1 I 2 I 3 Q I 5 Q I 4 Q

示例输出

1 2 3

问题二：寻找大富翁

在乌镇，共有n个人，我们需要找出该镇上前m个大富翁。输入包含多个测试用例，每个用例首先包含两个整数n和m，接着一行给出镇上n个人的财富值。

输入格式

输入包含多组测试用例。每个用例首先包含两个整数n（0 < n ≤ 100000）和m（0 < m ≤ 10），接下来一行输入镇上n个人的财富值。n和m同时为0时表示输入结束。

输出格式

输出前m个大富翁的财产数，财产多的排前面。如果大富翁不足m个，则全部输出。

示例输入

3 1 2 5 -1 5 3 1 2 3 4 5 0 0

示例输出

5 5 4 3

优先队列的使用

优先队列（Priority Queue）是一种数据结构，能够高效地进行插入和提取最大或最小的元素。在C++中，优先队列的实现通常基于堆（Heap）。以下是优先队列的基本操作和特性：

插入操作：在O(log n)时间复杂度内将元素插入队列。

提取最大元素：在O(log n)时间复杂度内提取队列中最大的元素。

比较方式：默认情况下，优先队列使用less比较方式，即队列中的元素从小到大排列。为了提取最大元素，需要将比较方式设置为greater。

在处理问题一时，我们需要确保优先队列中的元素始终不超过k个，这样在处理询问操作时，队列中总有k个元素可供选择。

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
#include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; int main() { int n, k, t; char s[5]; while (scanf("%d%d", &n, &k) != EOF) { priority_queue

, greater

> q; for (int i = 1; i <= n; ++i) { scanf("%s", s); if (s[0] == 'I') { scanf("%d", &t); q.push(t); if (q.size() > k) { q.pop(); } } else { printf("%d\n", q.top()); q.pop(); } } } return 0; }

代码解释

读取输入：使用scanf函数读取输入数据。首先读取n和k，然后处理接下来的n行数据。

优先队列初始化：使用priority_queue<int, vector<int>, greater<int>> q初始化一个优先队列，其中元素类型为int，容器为vector<int>，比较方式为greater

，即最大元素优先。

处理输入数据：对于每一行数据，如果是“I”，读取数字并将其添加到优先队列中。如果队列大小超过k，则弹出最小的元素。对于“Q”，则输出队列顶部的元素并弹出。

处理多个测试用例：当读取到n和m同时为0时，结束循环。

总结

优先队列在处理需要快速获取最大或最小元素的场景中非常有用。通过合理设置比较方式，可以确保队列的元素顺序符合需求。在处理问题一和问题二时，优先队列能够高效地管理和检索数据，从而解决问题。

转载地址：http://njnh.baihongyu.com/

你可能感兴趣的文章