#P3231. 打印任务排序(200分)
-
1000ms
Tried: 56
Accepted: 22
Difficulty: 5
所属公司 :
华为od
打印任务排序(200分)
题解
1. 题目理解与思路
给定一组打印任务的优先级,我们需要按照以下规则依次打印任务:
- 每次从队列头部取出第一个任务。
- 如果该任务的优先级是当前队列中最高的,则立即打印该任务。
- 否则,将该任务放到队列尾部,等待下次再处理。
我们需要输出每个任务的实际打印顺序。打印顺序是任务在整个队列中被打印的先后次序,从 0 开始编号。
2. 解题思路与优化
为了解决这个问题,我们可以采取以下步骤:
-
初始化任务队列:将输入的每个任务的优先级及其在原始输入中的索引保存在
deque中,以便模拟队列操作。 -
使用
vector维护当前优先级:- 将所有任务的优先级存入一个数组,并进行升序排序。我们可以利用排序数组的特性来快速找到当前的最大优先级。
- 在每次从队列头部取出任务后,检查它的优先级是否等于当前最高的优先级。
-
记录打印顺序:
- 使用一个数组
print_order记录每个任务的打印顺序,打印的顺序从0开始依次递增。
- 使用一个数组
-
输出结果:按照记录的顺序输出每个任务的打印顺序。
3. 复杂度分析
- 任务优先级的排序时间复杂度为
O(n log n)。 - 每次处理任务时的操作(如比较和查找)为
O(1),因此在处理所有任务时的总复杂度为O(n)。 - 因此,总的时间复杂度为
O(n log n)。
4. 问题本质分析
本题的核心在于模拟具有优先级的任务队列管理。通过将优先级存储在数组中,我们可以快速判断当前任务是否为最高优先级。这样的结构使得问题简化为简单的队列操作和数组查询,从而提高了效率。
5. 代码实现
Cpp
#include <bits/stdc++.h>
using namespace std;
void solve() {
string input_str;
getline(cin, input_str); // 读取整行输入
deque<pair<int, int>> task_queue; // (优先级, 原始索引)
stringstream ss(input_str);
string priority_str;
// 使用 vector 维护当前队列中的优先级并排序
vector<int> priority_list ;
// 解析输入字符串并生成任务队列
int task_index = 0;
while (getline(ss, priority_str, ',')) {
int priority = stoi(priority_str);
task_queue.push_back({priority, task_index++}); // (优先级, 原始索引)
priority_list.push_back(priority);
}
sort(priority_list.begin(), priority_list.end()); // 降序排序
vector<int> print_order(task_queue.size()); // 存储每个任务的打印顺序
int current_order = 0; // 记录打印的顺序号
while (!task_queue.empty()) {
auto [priority, index] = task_queue.front(); // 取队列头部任务
task_queue.pop_front(); // 移除头部任务
if (priority >= priority_list.back()) { // 检查是否为当前最大优先级
print_order[index] = current_order; // 记录任务的打印顺序
current_order++;
priority_list.pop_back(); // 移除最大优先级
} else {
// 否则,将任务放回队列尾部
task_queue.push_back({priority, index});
}
}
// 输出结果
for (size_t i = 0; i < print_order.size(); i++) {
if (i != 0) cout << ','; // 逗号分隔
cout << print_order[i];
}
}
int main() {
solve();
return 0;
}
Python
from collections import deque
def solve():
# 输入解析并生成任务队列
input_str = input().strip()
task_queue = deque()
priorities = list(map(int, input_str.split(',')))
for idx, priority in enumerate(priorities):
task_queue.append((priority, idx)) # (优先级, 原始索引)
# 使用列表维护当前队列中的优先级并排序
priority_list = sorted(priorities, reverse=True)
print_order = [0] * len(priorities) # 存储每个任务的打印顺序
current_order = 0 # 记录打印的顺序号
while task_queue:
priority, index = task_queue.popleft() # 取队列头部任务
if priority >= priority_list[0]: # 检查是否为当前最大优先级
print_order[index] = current_order # 记录任务的打印顺序
current_order += 1
priority_list.pop(0) # 从列表中移除该任务的优先级
else:
# 否则,将任务放到队列尾部
task_queue.append((priority, index))
# 输出结果
print(','.join(map(str, print_order)))
if __name__ == "__main__":
solve()
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String inputStr = scanner.nextLine(); // 读取整行输入
String[] prioritiesStr = inputStr.split(","); // 以逗号分隔输入
int n = prioritiesStr.length;
// 使用队列存储任务 (优先级, 原始索引)
Deque<int[]> taskQueue = new LinkedList<>();
List<Integer> priorityList = new ArrayList<>(); // 存储优先级列表
// 解析输入并生成任务队列
for (int i = 0; i < n; i++) {
int priority = Integer.parseInt(prioritiesStr[i]);
taskQueue.add(new int[]{priority, i}); // (优先级, 原始索引)
priorityList.add(priority);
}
// 升序排序优先级列表
Collections.sort(priorityList);
int[] printOrder = new int[n]; // 存储每个任务的打印顺序
int currentOrder = 0; // 记录打印的顺序号
while (!taskQueue.isEmpty()) {
int[] task = taskQueue.poll(); // 取队列头部任务
int priority = task[0];
int index = task[1];
if (priority >= priorityList.get(priorityList.size() - 1)) { // 检查是否为当前最大优先级
printOrder[index] = currentOrder; // 记录任务的打印顺序
currentOrder++;
priorityList.remove(priorityList.size() - 1); // 移除最大优先级
} else {
// 否则,将任务放回队列尾部
taskQueue.add(task);
}
}
// 输出结果
System.out.print(printOrder[0]);
for (int i = 1; i < printOrder.length; i++) {
System.out.print("," + printOrder[i]); // 逗号分隔
}
}
}
题目内容
某个打印机根据打印队列执行打印任务。打印任务分为九个优先级,分别用数字 1−9 表示,数字越大优先级越高。打印机每次从队列头部取出第一个任务 A,
然后检查队列余下任务中有没有比 A 优先级更高的任务,如果有比 A 优先级高的任务,则将任务 A 放到队列尾部,否则就执行任务 A 的打印。
请编写一个程序,根据输入的打印队列,输出实际的打印顺序。
输入描述
输入一行,为每个任务的优先级,优先级之间用逗号隔开,优先级取值范围是 1 ~ 9 。
输出描述
输出一行,为每个任务的打印顺序,打印顺序从 0 开始,用逗号隔开
样例1
输入
9,3,5
输出
0,2,1
说明
队列头部任务的优先级为 9 ,最先打印,故序号为 0;
接着队列头部任务优先级为 3 ,队列中还有优先级为 5 的任务,优先级 3 任务被移到队列尾部;
接着打印优先级为 5 的任务,故其序号为 1 ;
最后优先级为 3 的任务的序号为 2 。
样例2
输入
1,2,2
输出
2,0,1
说明
队列头部任务的优先级为 1 ,被移到队列尾部;接着顺序打印两个优先级为 2 的任务,故其序号分别为 0 和 1 ;最后打印剩下的优先级为 1 的任务,其序号为 2