问题描述
p12100原题链接：UVaOJ 12100 - Printer Queue
相关说明：本题为《算法竞赛入门经典（第2版）》习题 5-7
解法一：模拟 + 排序
使用一个 vector<int> 来维护所有的优先级（x 各自出现数量），排序以确保每次需要获取当前最高优先级值时能够从尾端获取。接下来要做的就是在优先级不是最高级时模拟更新队列状态，以及在优先级为最高级时的出队列 & 维护优先级 vector 操作，当取到需要的任务时，做个特殊处理。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#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; } |
|
1 |
#TODO |
