ZCMU--5121: 打印机队列

Description

老师办公室有一台神奇的打印机，而打印机的打印顺序则是一个队列。这个队列比较神奇，它能根据任务的优先级分配打印任务。

所有的任务有1-9的优先级（9的优先程度大于1），这个打印机的运作方式如下：

现有n堆有顺序的打印任务（每一个自己的任务都有自己的优先级），他们首先会按顺序进入打印队列，然后在打印的时候，打印机会判断这个任务的优先级，如果打印队列中有比当前打印任务优先级更高的任务的话，则会把当前打印任务重新放回打印队列的尾端。

此时，BaoBao想知道，第k个放进去的打印任务的完成时刻。

打印机完成第一份任务的时候是1时刻，第二份则是2时刻，以此类推。

Input

输入的第一行包含一个数字T(1≤T≤100)，代表有T组数据。每组数据仅包括两行。

每组数据第一行包括两个整数n(1≤n≤150),k(0≤k

第二行有n个整数ai​(1≤ai​≤9)，ai代表每份打印任务的优先级，按输入顺序进入打印队列。

Output

对于每组数据，输出一个整数，代表第k份打印任务的完成时刻。

Sample Input

4

1  0

5

4  2

1  2  3  4

6  0

2  1  9  1  1  1

6  0

1  1  9  1  1  1

Sample Output

1

2

2

5

解析：数据比较小，直接遍历模拟就ok，我们开两个数组a[ ]用来记录优先级，b[ ]来用记录是否是第K个，b[ i ]=1表示是所求的第K个放进去的，然后我们可以利用multiset来记录当前序列最大值，从i=0开始遍历，用c来计数打印了几个，看优先级是否是最大的。

如果是，那么就要打印，然后看看b[ i ]是不是1，是的话打印出来，break就ok，如果b[i]=0。那么就删除multiset最后一个元素。

如果不是，我们利用m来记录a[ ]的队尾下标，那么我们将a[ i ],b[ i ]复制到a[m],b[m]，m++，模拟移到队尾，如此直到找到第k个放入的那个任务。

#include 
#include 
using namespace std;
int a[1200],b[1200];//分别记录优先级和是否是第k个放入 
int main()
{
	int t,n,i,m,c,k;
	scanf("%d",&t);
	while(t--){
		multiset<int> st;
		scanf("%d%d",&n,&k);
		for(i=0;i
			scanf("%d",&a[i]);
			st.insert(a[i]);//插入set 
			if(i==k) b[i]=1;
			else b[i]=0;
		}
		i=0,c=0,m=n;//c来计数打印第几个，m记录队尾下标 
		while(1){
			if(a[i]==*st.rbegin()){//*st.rbegin()表示st最后一个元素的值，就是最大值 
				c++;
				if(b[i]==1){//是所求的第k个放入 
					printf("%d\n",c);
					break;
				}else i++,st.erase(--st.end());//删除一个最大值 
			}else a[m]=a[i],b[m++]=b[i++];//模拟移至队尾 
		}
		st.clear();
	}
	return 0;
}