C77-优先队列
原题链接：28705.NoteSC++
2025-10-08 12:14:44
发布于：江苏
5阅读
0回复
0点赞
一、作业部分
1.围圈报数
#include <bits/stdc++.h>
#include <queue>
using namespace std;
queue<int> q;
int n, m;
int main(){
cin >> n >>m;
for (int i=1; i<=n; i++) q.push(i);
for (int i=1; i<=n; i++){
//循环将m-1个人挪到队伍的最后
for (int j=1; j<=m-1; j++){
q.push(q.front());
q.pop();
}
cout << q.front() <<' ';
q.pop();
}
return 0;
}
/*
有n个人依次围成一圈，从第１个人开始报数，
数到第ｍ个人出列，
然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，
如此反复到所有的人全部出列为止。
设ｎ个人的编号分别为1，2，…，n打印出列的顺序。
输入格式
n和m。
输出格式
出列的顺序。
输入输出样例
输入#1
4 17
输出#1
1 3 4 2
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 5 6 7 8 ...
*/
//q.push()
//q.pop()
//q.empty()
//q.size()
//q.front()
//q.back()
2. 队列模拟
#include <bits/stdc++.h>
#include <queue>
using namespace std;
queue<int> q;
int n, t;
int main(){
cin >> n;
for (int i=1; i<=n; i++){
int op;
cin >> op;
if (1 == op){
cin >> t;
q.push(t);
}
if (2 == op){
if (q.empty()) cout<<"impossible!"<<endl;
else q.pop();
}
if (3 == op){
if (q.empty()) cout<<"impossible!"<<endl;
else cout<<q.front()<<endl;
}
}
return 0;
}
二、课堂案例
1. 发牌游戏
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int k, n, p;
queue<int> q;
int main(){
cin >> k >> n >> p;
for (int i=1; i<=k; i++){
q.push(i);
}
while (q.size()){
cout << q.front() << " ";
q.pop();
//循环往后移动p张
for (int i=1; i<=p; i++){
q.push(q.front());
q.pop();
}
}
return 0;
}
2. 优先队列
#include <bits/stdc++.h>
#include <queue>
using namespace std;
//queue<int> q;
//priority_queue<int> q; //默认从大到小， //大根堆
//priority_queue<int, vector<int>, less<int> > q; //默认从大到小， //大根堆
priority_queue<int, vector<int>, greater<int> > q; //从小到大， //小根堆
int main(){
int n;
cin >> n;
srand(time(0));
for (int i=1; i<=n; i++){
int t = rand()%100;
cout << t << ' ';
q.push(t);
}
cout << endl;
while (!q.empty()){
cout << q.top() << ' ';
q.pop();
}
return 0;
}
3. 合并果子
#include <bits/stdc++.h>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q; //从小到大， //小根堆
int n, t, ans;
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> t;
q.push(t);
}
//不停的合并直到变成一堆
while (q.size() >= 2){
int a = q.top(); q.pop();
int b = q.top(); q.pop();
ans += (a+b);
q.push(a+b); //将新合并的一堆果子重新入队
}
cout << ans;
return 0;
}
三、作业提示
本地电脑上写一个程序设置随机数种子3，随机生成100个对一千求余的元素。
srand(time(3)); //设置随机数种子
for (int i=1; i<=100; i++){
int t = rand()%1000;
这里空空如也
有帮助，赞一个