题目描述
某个打印机根据打印队列执行打印任务。打印任务分为九个优先级，分别用数字1-9表示，数字越大优先级越高。打印机每次从队列头部取出第一个任务A，
然后检查队列余下任务中有没有比A优先级更高的任务，如果有比A优先级高的任务，则将任务A放到队列尾部，否则就执行任务A的打印。
请编写一个程序，根据输入的打印队列，输出实际的打印顺序。
输入描述
输入一行，为每个任务的优先级，优先级之间用逗号隔开，优先级取值范围是1~9。
输出描述
输出一行，为每个任务的打印顺序，打印顺序从0开始，用逗号隔开
用例
| 输入 | 9,3,5 |
| 输出 | 0,2,1 |
| 说明 |
队列头部任务的优先级为9，最先打印，故序号为0； 接着队列头部任务优先级为3，队列中还有优先级为5的任务，优先级3任务被移到队列尾部； 接着打印优先级为5的任务，故其序号为1； 最后优先级为3的任务的序号为2。 |
| 输入 | 1,2,2 |
| 输出 | 2,0,1 |
| 说明 | 队列头部任务的优先级为1，被移到队列尾部；接着顺序打印两个优先级为2的任务，故其序号分别为0和1；最后打印剩下的优先级为1的任务，其序号为2 |
题目解析
关于用例2的输出解释：
初始时，每个任务的索引位置和优先级已经给定，因此我们可以将输入转化为：
[1, 0] // 优先级为1，初始排队序号为0
[2, 1] // 优先级为2，初始排队序号为1
[2, 2] // 优先级为2，初始排队序号为2
接下来开始打印头部任务[1, 0]，发现该任务的优先级不是最高的，因此需要将他取出压如队尾，即顺序变为：
[2, 1] // 优先级为2，初始排队序号为1
[2, 2] // 优先级为2，初始排队序号为2
[1, 0] // 优先级为1，初始排队序号为0
接下来开始打印头部任务[2, 1]，发现该任务的优先级是最高的，因此将他取出后打印，
即排队序号为1的任务，打印序号是0，剩余任务顺序如下：
[2, 2] // 优先级为2，初始排队序号为2
[1, 0] // 优先级为1，初始排队序号为0
继续取出头部任务[2, 2]，发现发现该任务的优先级是最高的，因此将他取出后打印，
即排队序号为2的任务，打印序号是1，剩余任务顺序如下：
[1, 0] // 优先级为1，初始排队序号为0
最后一个任务直接打印，即排队序号为0的任务，打印序号是2，
最后需要输出打印序号，但是需要按照排队序号的顺序输出。
排队序号为0的任务，打印序号是2，
排队序号为1的任务，打印序号是0
排队序号为2的任务，打印序号是1
通过上面逻辑的概述，我们可以使用链表结构来维护任务顺序，如下图所示：
[1, 0] → [2, 1] → [2, 2]
如果当前头部任务的优先级不是最高的，则取出后压入尾部
[2, 1] → [2, 2] → [1, 0]
如果当前头部任务的优先级是最高的，则取出
同时，为了记录打印序号，我们应该提前定义一个打印序号数组ans
比如上面头部[2, 1]取出后，说明排队序号1的任务，打印序号为0，即ans[1] = 0
还有一个问题，那就是如何判断当前头部任务的优先级是否是剩余任务中优先级最高的呢？
我的策略是，将输入的优先级，存入一个数组priority中，然后升序，假设一共n个任务，那么指针maxIdx = n – 1指向的就是最大优先级
初始时，我们只要对比链表头部任务的优先级是否等于priority[maxIdx]，
- 若等于，则当前链表头部的任务就是最高优先级，因此可以直接取出打印，而一旦打印，则maxIdx–，即让maxIdx指向剩余任务中最高的优先级
- 若不等于，则当前链表头部的任务不是最高优先级，不能打印，而是取出后需要重新加入链表尾部，此时maxIdx不变
Java算法源码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] priority = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
System.out.println(getResult(priority));
}
public static String getResult(int[] priority) {
int n = priority.length;
LinkedList<int[]> link = new LinkedList<>();
for (int i = 0; i < n; i++) {
link.add(new int[] {priority[i], i});
}
Arrays.sort(priority);
int maxI = n - 1;
int[] ans = new int[n];
int printIdx = 0;
while (link.size() > 0) {
int[] tmp = link.removeFirst();
int p = tmp[0], i = tmp[1];
if (p == priority[maxI]) {
ans[i] = printIdx;
printIdx++;
maxI--;
} else {
link.add(tmp);
}
}
StringJoiner sj = new StringJoiner(",");
for (int an : ans) {
sj.add(an + "");
}
return sj.toString();
}
}
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
const priority = line.split(",").map(Number); // 优先级，初始序号
console.log(getResult(priority));
});
function getResult(priority) {
const link = priority.map((ele, idx) => [ele, idx]);
priority.sort((a, b) => b - a);
let maxIdx = 0;
const n = priority.length;
const ans = new Array(n);
let printIdx = 0;
while (link.length > 0) {
const [p, i] = link.shift();
if (p == priority[maxIdx]) {
ans[i] = printIdx;
printIdx++;
maxIdx++;
} else {
link.push([p, i]);
}
}
return ans.join(",");
}
Python算法源码
# 输入获取
priorities = list(map(int, input().split(",")))
# 算法入口
def getResult():
link = [[p, i] for i, p in enumerate(priorities)]
n = len(priorities)
priorities.sort()
maxI = n - 1
ans = [0] * n
printIdx = 0
while len(link) > 0:
p, i = link.pop(0)
if p == priorities[maxI]:
ans[i] = printIdx
printIdx += 1
maxI -= 1
else:
link.append([p, i])
return ",".join(map(str, ans))
# 算法调用
print(getResult())
C算法源码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 1000
typedef struct {
int priority;
int idx;
} E;
typedef struct ListNode {
E *ele;
struct ListNode *next;
} ListNode;
typedef struct {
int size;
ListNode *head;
ListNode *tail;
} LinkedList;
LinkedList *new_LinkedList() {
LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
link->size = 0;
link->head = NULL;
link->tail = NULL;
return link;
}
void addLast_LinkedList(LinkedList *link, int priority, int idx) {
ListNode *node = (ListNode *) malloc(sizeof(ListNode));
E *e = (E *) malloc(sizeof(E));
e->priority = priority;
e->idx = idx;
node->ele = e;
node->next = NULL;
if (link->size == 0) {
link->head = node;
link->tail = node;
} else {
link->tail->next = node;
link->tail = node;
}
link->size++;
}
E *removeFirst_LinkedList(LinkedList *link) {
if (link->size == 0) exit(-1);
ListNode *removed = link->head;
if (link->size == 1) {
link->head = NULL;
link->tail = NULL;
} else {
link->head = link->head->next;
}
link->size--;
E *ele = (E *) malloc(sizeof(E));
ele->priority = removed->ele->priority;
ele->idx = removed->ele->idx;
free(removed);
return ele;
}
int cmp(const void *a, const void *b) {
return *((int *) a) - *((int *) b);
}
int main() {
int priority[MAX_SIZE];
int priority_size = 0;
while (scanf("%d", &priority[priority_size++])) {
if (getchar() != ',') break;
}
LinkedList *link = new_LinkedList();
for (int i = 0; i < priority_size; i++) {
addLast_LinkedList(link, priority[i], i);
}
qsort(priority, priority_size, sizeof(int), cmp);
int maxI = priority_size - 1;
int *ans = (int *) calloc(priority_size, sizeof(int));
int printIdx = 0;
while (link->size > 0) {
E *e = removeFirst_LinkedList(link);
int p = e->priority;
int i = e->idx;
if (p == priority[maxI]) {
ans[i] = printIdx;
printIdx++;
maxI--;
} else {
addLast_LinkedList(link, p, i);
}
}
char res[10000];
for(int i=0; i<priority_size; i++) {
char tmp[100];
sprintf(tmp, "%d", ans[i]);
strcat(res, tmp);
strcat(res, ",");
}
res[strlen(res) - 1] = ' ';
puts(res);
return 0;
}免责声明：
评论0