洛谷-UVA12100 打印队列 Printer Queue

题目描述

PDF

format_png

输入格式

format_png 1

输出格式

format_png 2

题意翻译

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

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

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

Translated by @HuangBo

思路：

第一步、
此题的重心是在判断任务的优先级，而任务本身可以忽略，因为在初始化的为任务设置优先级的时候，任务的编号默认从0、1、2、3…，因此通过编号作为数组下标创建数组，保留其任务的优先级。
第二步、
为其创建第二个数组保存排序后的优先级。
第三步、
模拟打印，打印当前任务时，在以自己编号作为下标的数组中，得到优先级判断是否大于或等于最高优先级且是否是我关注的打印任务，意思就是有3种情况，低于最高优先级、高于或等于最高优先级且不是我关注的、高于或等于最高优先级是我关注的。

输入输出样例

输入 #1复制

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

输出 #1复制

1
2
5
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    //数据条数 
    cin>>T;
    for(int i=0;i<T;i++){
        int n;//打印任务数量 
        int m; //我的任务编号 
        int x; //优先级 
        cin>>n>>m; 
        //q存储的是a数组的下标 
        queue<int> q;
        //a存储优先级，b优先级排序 
        vector<int> a,b;
        for(int j=0;j<n;j++){
            //各项任务的优先级 
            cin>>x;
            a.push_back(x);
            b.push_back(x);
            q.push(j);
        }
        //对b排序
        sort(b.begin(),b.end(),greater<int>()); //降序(默认升序)
        //思路判断a存储的优先级，是否为最高优先级，如果是则让q出队。 
        int w=0;//指向当前队列最高优先级的下标 
        int max=0;//读取队列最高优先级 
        int time=0;//完成个数 
        while(!q.empty()){
            max=b[w];
            int t=q.front();
            if(a[t]<max){
                q.pop();
                q.push(t); 
            } else{
                if(t==m){
                    cout<<++time<<endl;
                    break;
                }else{
                    q.pop();
                    time++;
                    w++;
                }
            }
        } 
    }
}