题解

1. 题目理解与思路

给定一组打印任务的优先级，我们需要按照以下规则依次打印任务：

• 每次从队列头部取出第一个任务。
• 如果该任务的优先级是当前队列中最高的，则立即打印该任务。
• 否则，将该任务放到队列尾部，等待下次再处理。

我们需要输出每个任务的实际打印顺序。打印顺序是任务在整个队列中被打印的先后次序，从 0 开始编号。

2. 解题思路与优化

为了解决这个问题，我们可以采取以下步骤：

1. 初始化任务队列：将输入的每个任务的优先级及其在原始输入中的索引保存在 deque 中，以便模拟队列操作。

2. 使用 vector 维护当前优先级：

   • 将所有任务的优先级存入一个数组，并进行升序排序。我们可以利用排序数组的特性来快速找到当前的最大优先级。
   • 在每次从队列头部取出任务后，检查它的优先级是否等于当前最高的优先级。

3. 记录打印顺序：

   • 使用一个数组 print_order 记录每个任务的打印顺序，打印的顺序从 0 开始依次递增。

4. 输出结果：按照记录的顺序输出每个任务的打印顺序。

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$