题目描述

WZK 去一家打印店，这家打印店对于若干个任务都有一个优先级（1~ 9，9 最高）。

现在，有 n 项打印任务在队列，以 0~ n-1 标号，0 为队首，每次若队首任务优先级是最高的（并列也算），则执行队首任务，否则把它重新放入队尾。

WZK 的某个打印任务也在其中，他想知道自己的打印任务需要多少时间才能完成。

假设每打印一个任务需要 1 个单位时间，移动任务不需要时间。

输入格式

第一行两个整数 n，m，表示总的任务数，m 表示 WZK 的打印任务。

接着一行 n 个整数，表示 0~ n-1 号人物的优先级。

数据范围

对于 100% 的数据，m <= n <= 100

输出格式
输出一行一个正数，即需要的时间。

样例

6 0 
1 1 9 1 1 1

5

解题思路分析

题目讲述的作业调度方式就是队列的知识，所以，这一部分的操作就使用队列数据结构。队列的元素应该是一个结构体，因为要记录每一份作业的序号的，后面要基于这个需要来判断是不是打印了 WZK 的哪一份作业（如果是，就任务结束）。

难点在于，如何知道队首的这个作业是不是优先级最高的作业。如果用笨方法，就是每次都把队列里面的所有元素查一遍，本题的数据量很小，所以也不会超时的。但是，我们有更好的办法。

我们可以把数据拷贝多一份出来，然后按照优先级排排序。按照题目说的打印规则，将来打印的时候的每一份作业的优先级一定会和这份排序好的数据的优先级一致。

例如，有这么一些作业，优先级是：{1,5,3,4,5,7,3,9,9}，那么将来打印作业的优先级顺序一定就是{9,9,7,5,5,4,3,3,1}。既然我们能得到这个优先级顺序，我们就可以根据这个来判断队首的作业是不是未打印作业里面优先级最高的。

完善程序

#include<bits/stdc++.h>
using namespace std;
struct task
{
	int priority; // priority 的英文是优先级的意思 
	int id;
}q[10001],x[10001];
bool cmp(task i,task j)
{
	return i.priority>j.priority;
}
int n,m,head,tail,sum,p;
int main()
{
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x[i].priority);
		x[i].id=i;
		q[ 填空(1) ] = x[i]; // 把 x[i] 放入队列 
	}

	sort(x,x+n,cmp);  //对 x 数组按照优先级排序，将来，打印的时候的顺序会和y数组的优先级顺序一致 

	p= 填空(2);  // p 是指向 x 数组的一个指针，下一份要打印的任务的优先级是x[p].priority 
	while(1) // 一定不是在这地方结束循环的，所以可以设成死循环
	{
		if(q[head].priority==填空(3)) //q[head]是剩下的任务中优先级最高的，可以打印
		{
			sum++;  //即便这个任务就是任务 m，打印也需要花时间，所以放在打印之前做sum++ 
			if(填空(4)==m)
			{
				printf("%d",sum);
				return 0;
			}
			填空(5); // q[head]出队列
			填空(6);  //p指针也要移动一下，为下一次比较做准备 
		}
		else // x[head]不是剩下的任务中优先级最高的，要把它放到最后尾
			q[填空(7)] = q[填空(8)];
	}
	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}

填空(6): {{ input(6) }}

填空(7): {{ input(7) }}

填空(8): {{ input(8) }}