1. 消息队列(priority_queue)
题目描述
消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在这个过程中发生了一些事情，如鼠标单击、文本更改，系统将向队列添加一条消息。同时，如果队列中的消息不为空，进程将根据优先级值进行一个从队列中获取消息的循环。注意，优先级数字越低表示优先级越高。在这个问题中，您需要模拟消息队列，以便将消息放入消息队列并从消息队列中获取消息。
输入
输入中只有一个测试用例。每行都是一个命令，“get”或“put”，这意味着获取消息或放置消息。如果命令为“Put”，则有一个字符串表示消息名，两个整数表示参数和优先级。最多有60000个命令。请注意，一条消息可能出现两次或两次以上，如果两条消息具有相同的优先级，则先出现的消息将首先被处理。（即，相同优先级的FIFO。）处理到输入结束。
输出
对于每个“get”命令，在一行中输出从消息队列获取的命令以及名称和参数。如果队列中没有消息，则输出“Empty”。“Put”命令没有输出。
样例输入
GET
PUT msg1 10 5
PUT msg2 10 4
GET
GET
GET
样例输出
EMPTY
msg2 10
msg1 10
EMPTY
题解
#include<bits/stdc++.h> using namespace std; struct node{ int num,level; string name; node(string name,int num,int level):name(name),num(num),level(level){} bool operator <(const node& rhs)const{ return level > rhs.level; } int main() { priority_queue<node> q; string op; string name; int num,level; while(cin>>op){ if(op == "PUT"){ cin >> name>>num>>level; q.push(node(name,num,level)); } if(op == "GET"){ if(!q.empty()){ node now = q.top(); q.pop(); cout<<now.name<<" "<<now.num<<endl; }else{ cout<<"EMPTY\n"; } } } }
2. 矩形排序（优先队列）
题目描述
使用优先队列实现把输入的多个矩形按面积降序输出，假定矩形面积互不相等
要求
1、矩形封装成类对象
2、优先队列的数据类型是矩形类
3、使用优先队列按面积降序输出矩形信息
提示：如果优先队列的数据类型不是标准类型，需要重载<运算符。
输入
第一行输入n表示矩形个数
接着输入n行，每行输入矩形的名称、长、宽
输出
按要求输出，每个矩形输出一行，参考输出样例
样例输入
5
aaa 2 3
bbb 3 4
ccc 4 5
ddd 5 3
eee 4 4
样例输出
ccc–20
eee–16
ddd–15
bbb–12
aaa–6
题解
#include<bits/stdc++.h> using namespace std; class rectangle { private: string name; int a, b; public: rectangle() { ; } rectangle(string n, int x, int y) { name = n; a = x; b = y; } void display()const { cout << name << "--" << a * b << endl; } bool operator <(const rectangle &r)const { return this->a * this->b < r.a * r.b; } }; int main() { int t; cin >> t; priority_queue<rectangle> group; while(t--) { string name; int a, b; cin >> name >> a >> b; rectangle r(name, a, b); group.push(r); } while(!group.empty()) { group.top().display(); group.pop(); } return 0; }
3. 赫夫曼树的构建(priority_queue)
题目描述
Huffman树在编码中有着广泛的应用。 在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
重复步骤1，直到{pi}中只剩下一个数。 在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。 本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。 例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入
输入的第一行包含一个正整数n（n<=100）。 接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59
题解
#include<bits/stdc++.h> using namespace std; int n; struct node{ int num,id; public: bool operator <(const node& rhs)const{ return num>rhs.num; } }; int main() { priority_queue<int,vector<int>,greater<int> > q; cin >> n; int a,tot=n+1; for(int i = 1; i <= n; i++){ cin>>a; q.push(a); } int sum = 0; while(q.size()>1){ int top1 = q.top();q.pop(); int top2 = q.top();q.pop(); sum += (top1+top2); q.push(top1+top2); } cout<<sum<<endl; }
4. 众数(map)
题目描述
所谓众数，就是对于给定的含有N个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中的重数最大的元素称为众数。例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。
对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。
输入
第一行为n，表示测试数据组数。(n<30)
每组测试的第一行是一个整数m，表示多重集S中元素的个数为m
接下来的一行中给出m(m<100)个不大于10万的自然数
（不会出现不同元素出现的次数相同的情况，如：S={11,11,22,22,33,33}）。
输出
每组测试数据输出一行，包含两个数，第一个是众数，第二个是其重数，中间以空格隔开。
样例输入
1
6
1 2 2 2 3 5
样例输出
2 3
题解
#include<bits/stdc++.h> using namespace std; int n, num; map<int,int> mp; int main() { int t; cin >> t; while(t--){ mp.clear(); cin >> n; for(int i = 0; i < n; i++){ cin >> num; mp[num]++; } int mx=0,cnt=0; for(auto i:mp){ if(i.second > cnt){ mx = i.first; cnt = i.second; } } cout<<mx<<" "<<cnt<<endl; } }
5. 上网记录统计(map)
题目描述
在一个网络系统中有 n(0<n<100)个用户、m(0<m<1000)次上网记录。每个用户一个账号，是一个长度小于 20的字符串。每个账号每次上网都会浏览网页，网页名是以一个长度小于100 的字符串。假设日志文件记录了账号浏览网页记录，请根据这些记录统计每个账号浏览了哪些网页。
输入
测试数据有多组
每组测试数据格式如下：
m (上网记录数)
2~m+1行，每行一条记录: 账号 网页（中间以空格分隔。账号，网页中间没空格）
输出
对每组测试数据，输出各账号的访问网页信息（按访问顺序，中间以空格分隔，具体见输出样例)。各组数据间以空行分隔。
样例输入
10
liuyidao https://www.sohu.com/
liuyidao https://www.sina.com.cn/
shenzhenwa https://cloud.tencent.com/
liuyidao https://www.bilibili.com/
shenzhenwa https://www.baidu.com/
shendaxuezi www.cplusplus.com
shendaxuezi https://www1.szu.edu.cn/
liuyidao www.cplusplus.com
shendaxuezi www.cplusplus.com
shenzhenwa https://news.qq.com/mobile/
样例输出
liuyidao https://www.sohu.com/https://www.sina.com.cn/https://www.bilibili.com/ www.cplusplus.com
shenzhenwa https://cloud.tencent.com/https://www.baidu.com/https://news.qq.com/mobile/
shendaxuezi www.cplusplus.com https://www1.szu.edu.cn/ www.cplusplus.com
题解
#include<bits/stdc++.h> using namespace std; int n, m,tot; map<string,int> table; vector<string> names; vector<string> mp[105]; int main() { while(cin >> m){ names.clear(); for(int i = 0; i < m;i++) mp[i].clear(); tot=0; string name,web; for(int i = 0; i< m; i++){ int now; cin>>name>>web; if(table.find(name)==table.end()){ now = tot; table[name]=tot++; names.push_back(name); }else now = table[name]; mp[now].push_back(web); } for(int i=0; i < tot; i++){ cout<<names[i]<<" "; for(int j = 0;j<mp[i].size();j++){ cout<<mp[i][j]<<" \n"[j==mp[i].size()-1]; } } cout<<endl; } }
