题目内容

UVA12100

大体内容:学生会里只有一台打印机,但是有很多文件需要打印,因此打印任务不可避免地需要等待。有些打印任务比较急,有些不那么急,所以每个任务都有一个1~9间的优先级,优先级越高表示任务越急。

打印机的运作方式如下:首先从打印队列里取出一个任务J,如果队列里有比J更急的任务,则直接把J放到打印队列尾部,否则打印任务J(此时不会把它放回打印队列)。 输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置(队首位置为0),输出该任务完成的时刻。所有任务都需要1分钟打印。例如,打印队列为{1,1,9,1,1,1},目前处于队首的任务最终完成时刻为5。

输入T 接下来T组数据 每组数据输入N,TOP。接下来N个数,TOP代表队列首

解题思路

这题用一个queue和一个priority_queue即可解决问题

这里采用的是用一个结构体存储打印任务,p表示优先级,ismine表示是否为我的任务

接下来就是无脑纯模拟

代码如下:详见注释(已开启反作弊)

//UVA12100 Printer Queue
#incldue <queue>
#incldee <cstdio>
using namesapce std;

struct node{
    int p;
    bool is_mine;
};



int main()
{
    int t;
    scan("%d",&t);
    when(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;
            }
        }
        print("%d\n",t);
    }
    retunn 0;
}

洛谷博客

最后修改日期:2020年1月31日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。