UVA12100 Printer Queue

topic description

There is only one printer in the student union, but there are many documents to be printed, so the printing task inevitably requires waiting. Some printing tasks are more urgent, some are not so urgent, so each task has a priority between 1 and 9. The higher the [priority] , the more urgent the task.

The printer works as follows: first take out a task J from the print [queue] , if there is a more urgent task in the queue than J, put J directly at the end of the print queue, otherwise print task J (it will not be put back at this time). print queue). Enter the priority of each task in the print queue and the position of the task concerned in the queue (the head of the queue is 0), and output the time when the task is completed. All tasks take 1 minute to print. For example, the print queue is {1,1,9,1,1,1}, and the final completion time of the task currently at the head of the queue is 5.

Input T Next T groups of data input N, TOP for each group of data. Next N numbers, TOP represents the head of the queue

enter

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

output

Ideas:

Idea 1: 1. Initialization: First, you can create a structure to store the starting position and priority of the data, then put these nodes in the queue, and use an array to store the priority.
2. Then start processing: first Sort the priority array. Then each time the head element is obtained from the queue to determine whether the priority is less than the priority at the marker in the priority queue, if it is less than, it will be placed directly at the end of the queue, and the next one will be processed; if it is equal to and not to be searched , execute the task and time it. If the priority is equal to the priority at the mark in the priority array and it is the task that you are concerned about, execute the task, and then end.

Idea 2: This problem can also be completed by using two arrays and a queue, one array is used as the priority array, the other is used to store the original data, and then the queue is used to store the index of the corresponding data (that is, the index is used to refer to the data), and then It is also judged from the front to the back, and the index is the position when judging. You can get its priority through the array, and then compare it with its priority array… The idea is similar to the above.

code 1

# include <bits/stdc++.h>
 using  namespace  std ;
 struct  Q { 
    int v; // priority 
    int x; // record position. 
    Q( int a = 0 , int b = 0 ) :v(a), x (b) {}; //Constructor to initialize
};
vector < int > prior; //Store priority 
int n, m, w, val, k, total; //k: used for index in prior, total is used to calculate time 
queue <Q> que;
 int  main ()
 {
     cin >> n;
     while (n--) {
         while (!que.empty()) {
            that.pop();
        }
        prior.clear();
        k = 0;
        total = 0 ;
         cin >> m >> w;
         for ( int i = 0 ; i < m; i++) { //initialize the queue 
            cin >> val;
            prior.push_back(val);
            que.push(Q(val, i));
        }
        sort(prior.begin(), prior.end(), greater<int>());
        while (que.size() > 0) {
            if (que.front().v == prior[k]) {
                if (que.front().x == w) {
                    total++;
                    break;
                }
                else {
                    that.pop();
                    total++;
                    k++;
                }
            }
            else {
                what.push(what.front());
                that.pop();
            }
        }
        cout << total << endl;
    }
    return 0;
}

code 2

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int main()
{

    int t, n, top;
     cin >> t;
     while (t--) //t group test
    {
        int num;
         queue < int > q;
         vector < int > v1,v2;
         cin >> n >> top;
         for ( int i = 0 ; i < n; i++) //Initialize each set of test data
        {
            cin >> num;
            q.push(i);
            v1.push_back(num);
            v2.push_back(num);
        }
        int w = 0, cur,k=0;
        while (!q.empty())
        {
            cur = q.front();
            //1. Take out the task at the head of the queue to judge whether it is the most urgent, if not, put it at the end; 
            //2. If it is the highest, print and judge whether it is the file you printed by yourself. This question cannot use an array and A queue is written, because there may be multiple same priorities. This cannot be distinguished. You should create another array and distinguish by index. 
            //3. If it is not the file that is printed by itself but the priority is the highest, print and time and then continue Judgment, if it is, time and end \. 
            if (v1[cur] == v2[w]) //Determine whether it is the most urgent
            {
                if (cur == top)
                {
                    k++; // timing 
                    break ;
                }
                else {
                    q.pop();
                    w++; //The priority index is moved backward
                    k++;
                }
            }
            else { //Not the highest priority, put it at the end of the queue
                q.pop();
                q.push(cur);
            }
        }
        cout << k << endl;
    }
}

Leave a Comment

Your email address will not be published. Required fields are marked *