zg584_O-Z39663

全栈程序员站长

发布于 2022-09-22 19:59:50

2900

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

1396: 队列问题(2)

Time Limit: 1 Sec Memory Limit: 128 MB

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

1 0

4 2

1 2 3 4

6 0

1 1 9 1 1 1

Sample Output

【分析】

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.cn/169961.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https