【PTA数据结构 | C语言版】车厢重排

本专栏持续输出数据结构题目集，欢迎订阅。

题目

一列挂有 n 节车厢（编号从 1 到 n）的货运列车途径 n 个车站，计划在行车途中将各节车厢停放在不同的车站。假设 n 个车站的编号从 1 到 n，货运列车按照从第 n 站到第 1 站的顺序经过这些车站，且将与车站编号相同的车厢卸下。

货运列车的各节车厢以随机顺序入轨，为方便列车在各个车站卸掉相应的车厢，须重排这些车厢，使得各车厢从前往后依次编号为 1 到 n，这样在每个车站只需卸掉当前最后一节车厢即可。

车厢重排可通过转轨站完成。一个转轨站包含一个入轨，一个出轨和 k 个位于入轨和出轨之间的缓冲轨。缓冲轨用于存储尚未确定输出次序的车厢。重排车厢的规则包含如下三条：

1.一个车厢从入轨移至出轨或缓冲轨；
2.一个车厢只有在其编号恰是下一个待输出编号时，可移到出轨；
3.一个车厢移到某个缓冲轨，仅当其编号大于该缓冲轨中队尾车厢的编号，若多个缓冲轨满足这一条件，则选择队尾车厢编号最大的，否则选择一个空缓冲轨，若无空缓冲轨则无法重排。

请你编写程序实现这个重排算法。

输入格式：
输入在第一行中给出两个正整数 n 和 k，均不超过 100，分别为车厢数量和缓冲轨数量。第二行按入轨顺序给出 n 节车厢的编号，数字间以空格分隔。

输出格式：
按照车厢进入出轨的顺序，输出每节车厢在入轨时的位序（从 0 开始），每个数字占一行。若无法重排，则在一行中输出信息 错误：任务不可能完成。。

输入样例 1：
9 3
5 8 1 7 4 2 9 6 3

输出样例 1：
2
5
8
4
0
7
3
1
6

输入样例 2：
9 2
5 8 1 7 4 2 9 6 3

输出样例 2：
错误：任务不可能完成。

代码

#include <stdio.h>
#include <stdlib.h>#define MAX_N 1000
#define MAX_K 100typedef struct {int data[MAX_N];int front;int rear;
} Deque;void dequeInit(Deque *dq) {dq->front = 0;dq->rear = 0;
}int dequeIsEmpty(Deque *dq) {return dq->front == dq->rear;
}void dequePushBack(Deque *dq, int value) {dq->data[dq->rear++] = value;
}int dequePopFront(Deque *dq) {return dq->data[dq->front++];
}int dequePeekFront(Deque *dq) {return dq->data[dq->front];
}int dequePeekBack(Deque *dq) {return dq->data[dq->rear - 1];
}int main() {int n, k;scanf("%d %d", &n, &k);Deque inTrain;dequeInit(&inTrain);int input[MAX_N];for (int i = 0; i < n; i++) {scanf("%d", &input[i]);dequePushBack(&inTrain, input[i]);}Deque bufferTrain[MAX_K];for (int i = 0; i < k; i++) {dequeInit(&bufferTrain[i]);}int curOut = 1;int num = 0;int outTrain[MAX_N];int outIdx = 0;while (num < n) {int cur = 0;if (!dequeIsEmpty(&inTrain)) {cur = dequePeekFront(&inTrain);}if (cur == curOut) {dequePopFront(&inTrain);for (int i = 0; i < n; i++) {if (input[i] == cur) {outTrain[outIdx++] = i;break;}}curOut++;num++;} else {int cnt = 0;for (int i = 0; i < k; i++) {if (!dequeIsEmpty(&bufferTrain[i])) {int head = dequePeekFront(&bufferTrain[i]);if (head == curOut) {cnt = 1;dequePopFront(&bufferTrain[i]);for (int j = 0; j < n; j++) {if (input[j] == head) {outTrain[outIdx++] = j;break;}}curOut++;num++;break;}}}if (cnt == 0) {int max = 0;for (int i = 0; i < k; i++) {if (!dequeIsEmpty(&bufferTrain[i])) {int tail = dequePeekBack(&bufferTrain[i]);if (cur > tail && tail > max) {max = tail;cnt = i;}}}if (max == 0) {for (int i = 0; i < k; i++) {if (dequeIsEmpty(&bufferTrain[i])) {dequePushBack(&bufferTrain[i], cur);dequePopFront(&inTrain);cnt = 1;break;}}if (cnt == 0) {printf("错误：任务不可能完成。\n");return 0;}} else {dequePushBack(&bufferTrain[cnt], cur);dequePopFront(&inTrain);}}}}if (num == n) {for (int i = 0; i < n; i++) {printf("%d\n", outTrain[i]);}}return 0;
}