大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
1396: 队列问题(2)
Time Limit: 1 Sec
Memory Limit: 128 MB
[
Submit][
Status][
Web Board]
Description
有一个含有n个元素的队列q，每个元素的大小满足1<=xi<=9(0<i<n)。队列有一种操作，对于队首元素若是整个队列最大的则出队列，否则加入队尾。对于一个给定的m，你能告诉我xm是第几个出队列的吗？
Input
输入数据第一行是一个整数T(1<=T<=1000)，表示输入数据的组数；每组数据的第一行是两正整数n表示队列的大小和第几个元素(1<n<=1000，0<=m<n)，第二行有n个数xi ，分别代表每个元素的大小。
Output
对于每组测试数据，输出xm是第几个出队列。
Sample Inp
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
Sample Output
1
2
5
【分析】
stl的练习题，multset是不会判重的set，用来记录当前最大值即可，因为set本身是升序，所以需要重载比较命令greater<int>
然后就是按照题目所说的queue直接模拟即可，因为要找到第i个，所以可以在第i个元素后面插入一个-1作为标记，若某一次pop操作之后队首是-1，那么说明第m个元素已经被弹出了，这时候输出答案就可以了
【代码】
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
queue<int>a;
multiset<int,greater<int> >b;
int main()
{
int pp;scanf("%d",&pp);
while (pp--)
{
int n,m;scanf("%d%d",&n,&m);
while (!a.empty()) a.pop();
b.clear();
for (int i=0;i<n;i++)
{
int x;scanf("%d",&x);
a.push(x);
b.insert(x);
if (i==m) a.push(-1);
}
int ans=0;
while (1)
{
//printf("%d**%d\n",a.front(),*b.begin());
if (a.front()==*b.begin())
{
ans++;
a.pop();
b.erase(b.begin());
if (a.front()==-1) break;
}
else
{
a.push(a.front());
a.pop();
}
}
printf("%d\n",ans);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/169961.html原文链接：https://javaforall.net
