UVaOJ 12100 - Printer Queue

问题描述

解法一：模拟 + 排序

使用一个 vector<int> 来维护所有的优先级（x 各自出现数量），排序以确保每次需要获取当前最高优先级值时能够从尾端获取。接下来要做的就是在优先级不是最高级时模拟更新队列状态，以及在优先级为最高级时的出队列 & 维护优先级 vector 操作，当取到需要的任务时，做个特殊处理。

#include <bits/stdc++.h>

using namespace std;

int main () {
    int t, priority; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        vector<int> prioritys;
        queue<pair<int, int>> tasks;  // first: position, second: priority
        for (int i = 0; i < n; i++) {
            cin >> priority;
            tasks.push({i, priority});
            prioritys.push_back(priority);
        }
        sort(prioritys.begin(), prioritys.end());  // .back() is the largest
        int minutes = 0;
        while (!tasks.empty()) {
          while (tasks.front().second != prioritys.back()) {
            tasks.push(tasks.front());
            tasks.pop();
          }
          if (tasks.front().first == m) {
            cout << minutes + 1 << endl;
            break;
          }
          tasks.pop();
          prioritys.pop_back();
          minutes++;
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main () {

int t, priority; cin >> t;

while (t--) {

int n, m; cin >> n >> m;

vector<int> prioritys;

queue<pair<int, int>> tasks; // first: position, second: priority

for (int i = 0; i < n; i++) {

cin >> priority;

tasks.push({i, priority});

prioritys.push_back(priority);

}

sort(prioritys.begin(), prioritys.end()); // .back() is the largest

int minutes = 0;

while (!tasks.empty()) {

while (tasks.front().second != prioritys.back()) {

tasks.push(tasks.front());

tasks.pop();

}

if (tasks.front().first == m) {

cout << minutes + 1 << endl;

break;

}

tasks.pop();

prioritys.pop_back();

minutes++;

}

return 0;

}

#TODO

#TODO

AOAPC II UVaOJ