MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 12100 - Printer Queue
AOAPC II

UVaOJ 12100 - Printer Queue

Chai
2021-11-24 0:00:00在线评测阅读 481

问题描述

p12100

原题链接:UVaOJ 12100 - Printer Queue

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-7

解法一:模拟 + 排序

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

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz