打印队列(Printer Queue)(优先队列)

刺骨的言语ヽ痛彻心扉 2022-11-30 12:58 288阅读 0赞

学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9间的优先级，优先级越高表示任务越急。  
打印机的运作方式如下：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。  
输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为\{1,1,9,1,1,1\}，目前处于队首的任务最终完成时刻为5。  
输入T  
接下来T组数据  
每组数据输入N，TOP。接下来N个数，TOP代表队列首  
输入输出样例  
输入  
3  
1 0  
5  
4 2  
1 2 3 4  
6 0  
1 1 9 1 1 1  
输出  
1  
2  
5

#include <queue>
    #include <cstdio>
    using namespace std;
    struct node
    { 
        int p;
        bool is_mine;
    };
    int main()
    { 
        int t;
        scanf("%d",&t);
        while(t--)
        { 
      	queue<node> q;
      	priority_queue<int> q2;//优先队列
      	int n,m;
      	scanf("%d %d",&n,&m);
      	for(int i=0;i<n;i++)
      	{ 
                int x;
                scanf("%d",&x);
                q.push((node){ x,i==m});
                q2.push(x);
      	}
      	int t=0;
      	while(!q.empty())//当打印队列不为空时
      	{ 
                node x=q.front();//每次先取出一个任务
                q.pop();
                if(x.p==q2.top())//判断是否有更高优先级
                { 
        		t++;
        		q2.pop();
        		if(x.is_mine) break;//如果是我要打印的任务，结束循环并输出
        		else continue;
                }
       	    else
                { 
        		q.push(x);//将任务放回队尾
        		continue; 
                }
      	}
      	printf("%d\n",t);
        }
        return 0;
    }