大一寒假训练:队列

发布于:2021-10-24 07:16:29

一、使用

C++队列queue模板类的定义在头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。


C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。

C++队列Queue类成员函数如下:


back()返回最后一个元素


empty()如果队列空则返回真


front()返回第一个元素


pop()删除第一个元素


push()在末尾加入一个元素


size()返回队列中元素的个数


queue 的基本操作举例如下:


queue入队,如例:q.push(x); 将x 接到队列的末端。


queue出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。


访问queue队首元素,如例:q.front(),即最早被压入队列的元素。


访问queue队尾元素,如例:q.back(),即最后被压入队列的元素。


判断queue队列空,如例:q.empty(),当队列空时,返回true。


访问队列中的元素个数,如例:q.size()


二、*题&题解(共七题)
周末舞会-队列

#include
using namespace std;
int n, m, t;
queue s1,s2;

int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= n; i++)
s1.push(i);
for (int i = 1; i <= m; i++)
s2.push(i);
for (int i = 1; i <= t; i++)
{
cout << s1.front() << " " << s2.front() << endl;
s1.push(s1.front());
s1.pop();
s2.push(s2.front());
s2.pop();
}
//system("pause");
return 0;
}

报数-队列-约瑟夫环

#include
using namespace std;
int n, m, t = 1;
queue s;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
s.push(i);
while (s.size() != 1)
{
if (t == m)
{
s.pop();
t = 1;
}
else
{
s.push(s.front());
s.pop();
t++;
}
}
cout << s.front();
//system("pause");
return 0;
}

取牌游戏-队列-SET

#include
using namespace std;
int n, k, p, cnt, t, pos;
queue s;
int main()
{
cin >> n >> k >> p;
int str[100050];
for (int i = 1; i <= k; i++)
s.push(i);
while (!s.empty())
{
cnt++;
t = s.front();
s.pop();
if (cnt % n == 0)
str[pos++] = t;
for (int i = 1; i <= p; i++)
{
s.push(s.front());
s.pop();
}
}
sort(str, str + pos);
for (int i = 0; i < pos; i++)
cout << str[i] << endl;
//system("pause");
return 0;
}

酒桌游戏-队列

注意题目条件别看掉了,“含7和7的倍数”


#include
using namespace std;
int n, m, t;
queue s;
string str;
bool check(int a) //检查是否含7
{
int y;
while (a)
{
y = a % 10;
if (y == 7)
return 1;
a = a / 10;
}
}
int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= n; i++)
{
cin >> str;
s.push(str);
}
int k = m - 1;
while (k--)
{
s.push(s.front());
s.pop();
}
while (s.size() != 1)
{
if (t % 7 == 0 || check(t))
{
s.pop();
t++;
}
else
{
s.push(s.front());
s.pop();
t++;
}
}
cout << s.front();
//system("pause");
return 0;
}

海港-队列

这题主要是要想到对每个人的信息存入结构体


#include
using namespace std;
int n, t, k, ans, x, str[500000], pub;
struct xinxi
{
int t;
int x;
} xx;
queue s;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
while (n--)
{
cin >> t >> k;
for (int i = 1; i <= k; i++)
{
cin >> x;
s.push({t, x});
if (str[x] == 0)
ans++;
str[x]++;
}
while (t - s.front().t >= 86400)
{
xx = s.front();
s.pop();
pub = xx.x;
str[pub]--;
if (str[pub] == 0)
ans--;
}
cout< }
//system("pause");
return 0;
}

Blash数集-队列-set

这题注意,我这种写法用优先队列是为了在队列就按升序排列,再存入集合中。如果是普通的序列,会出现上界值答案错误的情况,因为队列中第1e5个数后面的数不一定都大于前面1e5个数。


#include
using namespace std;
typedef long long ll;
set ssr;
set::iterator it; //这里不能it = ssr.begin();因为ssr里目前没有存值,内存指向会出问题
priority_queue,greater >s;

int t1, t2, a, n, cnt = 1;
int main()
{
cin >> a >> n;
s.push(a);
while (ssr.size() <= 1e5)
{
int t = s.top();
t1 = 2 * t + 1;
t2 = 3 * t + 1;
ssr.insert(t);
s.pop();
s.push(t1);
s.push(t2);
}
n = n - 1;
it = ssr.begin();
while (n--)
it++;
cout << *it << endl;
//system("pause");
return 0;
}

关系网络-队列(队列实现BFS)

这里需要补充一下深搜(DFS)广搜(BFS) 的内容:


1.概述
2.搭配使用效果更佳

#include
using namespace std;
int n, x, y, str[101][101], f[101];
struct xinxi
{
int x, cnt;//记录找到的人序号、当前步数
} xx;
queue s;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> str[i][j];
s.push({x, 0}); //出发点入列
f[x] = 1;//入列标记
while (!s.empty())//队列实现BFS:出发点入列 -> 取去队首 -> 判定 -> 搜索邻接点,步数+1并标记
{
int tprx = s.front().x;
int cnt = s.front().cnt; //取队首
s.pop(); //去队首
if (tprx == y)
{
cout << cnt - 1 << endl;//因为每找道一个认识的人cnt都+1,那么当找到y时也+1了,所以得减去
break;
}
for (int i = 1; i <= n; i++)
{
if (str[tprx][i] && !f[i])//str[tprx][i]=1且f[i]=0(未被标记)
{
f[i] = 1;
s.push({i, cnt + 1});
}
}
}
//system("pause");
return 0;
}

相关推荐

最新更新

猜你喜欢