UVA 12100 Printer Queue(队列，优先队列)-蒲公英云

UVA 12100 Printer Queue(队列，优先队列)

朱雀 2022-06-07 02:26 296阅读 0赞

详细题目：https://vjudge.net/problem/UVA-12100

思路：

用队列模拟，开一个的队列，分别表示任务的优先级和位置。再开一个的优先队列，默认任务的优先级为从大到小的优先顺序。

每次取出队列首任务，若其优先级不是最高的（根据优先队列判断），将其入队；否则，ans++，再判断其位置是否为所求任务完成的时刻，若是则输出ans结束。

#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
struct node
{
    int pri,pos;
};
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        queue<node> q;
        priority_queue<int> pq;
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            node a;
            cin>>a.pri;
            a.pos=i;
            q.push(a);
            pq.push(a.pri);
        }
        node x;
        int ans=0,tp;
        while(1)
        {
            x=q.front();
            q.pop();
            tp=pq.top();
            if(x.pri==tp)
            {
                pq.pop();
                ans++;
                if(x.pos==k)
                {
                    cout<<ans<<endl;    break;
                }
            }
            else
                q.push(x);
        }
    }
    return 0;
}