ZCMU--1396: 队列问题(2)

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 Input

3

1  0

5

4  2

1  2  3  4

6  0

1  1  9  1  1  1

Sample Output

1

2

5

解析：我们利用set来快速得出当前队列中最大元素值，因为有元素重复，所以我们得用multiset来存。我们可以用结构体来存元素的id和valu值，c表示第几个出列，如果a[ i ]==st.*rbegin()表示a[ i ]是当前队列中最大的元素，出列，如果是xm，那么就输出c即可，反之不是最大值，就到队尾，对应multiset中也要删除该元素，如此反复直到xm出列。

#include <stdio.h>
#include <set>
using namespace std;
struct su
{
	int id;
	int v;
}a[10005];
int main()
{
	int t,i,n,k,c;
	scanf("%d",&t);
	while(t--){
		multiset<int>st;	//建立multiset 
		scanf("%d%d",&n,&k);
		c=1;		//表示第几个出列 
		for(i=0;i<n;i++){
			scanf("%d",&a[i].v);
			a[i].id=i;
			st.insert(a[i].v);	//存入set 
		}
		for(i=0;i<n;i++){
			if(a[i].v==*st.rbegin()){	//表示是当前队列最大值 
				if(a[i].id==k){		//刚好是xm 
				printf("%d\n",c); 
				break;
			}else st.erase(--st.end()),c++;	//删除最后一个元素，也就是最大值 
			}else{	//不是最大值，模拟到队尾 
				a[n].v=a[i].v; 
				a[n++].id=a[i].id;
			}
		}
		st.clear();
	}
	return 0;
}