本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

一列掛有 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;
}