打印任务排序
#容器的应用 2025-03-04 
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>
#include <unordered_set>
#include <sstream>
using namespace std;

struct Task {
  int level_;
  int index_;
  int out_index = 0;

  Task(int level, int index) : level_(level), index_(index) {}

  bool operator<(const Task &right_task) const {
	  return this->level_ < right_task.level_;
  }

  bool operator==(const Task &right_task) const {
	  return this->level_ == right_task.level_;
  }
};

int main() {
	string data;
	getline(cin, data);
	list<Task> taskList;
	priority_queue<Task> taskPQue;

	istringstream iss(data);
	string level;
	int index = 0;
	while (getline(iss, level, ',')) {
		Task task(stoi(level), index);
		taskList.push_back(task);
		taskPQue.push(task);
		index++;
	}

	// 遍历优先级，更新 taskVec 的 out_index 并记录到 ResultList
	int out_index = 0;
	list<Task> ResultList;
	while (!taskPQue.empty()) {
		for (Task &task : taskList) {
			auto it = std::find(taskList.begin(), taskList.end(), task);
			if (taskPQue.top() == task) {
				task.out_index = out_index++;
				ResultList.push_back(task);
				taskPQue.pop();
				taskList.erase(it);
				break;
			}
			// 只要不相等，那就往后移到末尾
			taskList.splice(taskList.end(), taskList, it);
			break;
		}
	}

	ResultList.sort([](const Task &l_task, const Task &r_task) -> bool {    // 根据 index 排序，按原始顺序输出
	  return l_task.index_ < r_task.index_;
	});

	int i = 0;
	for (const Task &task : ResultList) {
		if (i > 0) cout << ",";
		cout << task.out_index;
		i++;
	}

	return 0;
}

我觉得这道题最唬人的就是题意，有必要讲清楚这个，但是官方给的示例又不妥当。

输入：3,2,3,2

输出：0,3,1,2

image20250304190220383.png

因此，这个时候我们把这个下标对应到原数组中去，按照原数组的顺序来输出这些下标。

image20250304190352410.png

对于优先级队列而言，它不需要关心是哪个具体的元素在前（我指那种两个相等元素），只按照等级大小来排序。

对于存储任务列表的容器，只要当前元素的等级小于优先队列的顶部元素，就把链表中当前元素后移，继续往下比较。