根據給定條件恢復洗牌佇列

---

在這個問題中，我們給出了角色名稱以及站在該角色前面更高的人數。

我們可以根據站在任何人前面更高的人數對人員的位置進行排序。之後，我們根據 nums[] 陣列的值更新每個人的位置，以獲得原始佇列。

問題陳述 - 我們給定了一個數組 persons[] 和 nums[]。persons[] 陣列包含人員的姓名，nums[] 陣列包含站在每個人前面更高的人數。此佇列已洗牌，我們需要找到原始佇列。

示例

輸入

persons[N] = {"pq", "rs", "tu", "vw"}; nums[N] = {0, 1, 0, 0};

輸出

pq 1, tu 2, vw 4, rs 3

說明 - ‘pq’ 是個子最矮的人。此外，‘tu’ 有 1 個更高的人站在他前面。

輸入

persons[N] = {"pq", "rs", "tu", "vw"}; nums[N] = {0, 2, 3, 3};

輸出

-1

說明 - 無法重新排列佇列。

方法

在這種方法中，我們將對人員姓名及其前面站立的更高人數的配對進行排序。之後，我們將更新每個人的位置以獲得更新的佇列。

演算法

步驟 1 - 定義 ‘pairs[]’ 陣列以儲存人員姓名及其給定數值的配對。

步驟 2 - 開始遍歷 persons[] 和 nums[] 陣列並將它們插入到 pairs 陣列中。

步驟 3 - 使用 sort() 方法對 pairs[] 陣列進行排序。

步驟 4 - 此外，定義 ‘res’ 列表，並開始遍歷 pairs[] 陣列。

步驟 5 - 如果 p - pairs[p].first 小於 0，則列印 -1，因為獲取原始佇列是不可能的。

步驟 6 - 否則，使用 temp 更新 res[p]。

步驟 7 - 現在，我們需要更新 res[q] 陣列中人員的位置。因此，開始遍歷 ‘res’ 陣列。

步驟 8 - 使用巢狀迴圈從 0 到 q 索引遍歷 res 陣列。

步驟 9 - 如果 res[q] 大於或等於 res[p]，則將 res[q] 加 1。

步驟 10 - 列印每個人的位置。

示例

#include <bits/stdc++.h>
using namespace std;

void FindOriginalQueue(string persons[], int nums[], int N) {
    pair<int, string> pairs[N];
    int res[N];
    // Insert elements to pairs[] array
    for (int p = 0; p < N; p++) {
        pairs[p].first = nums[p];
        pairs[p].second = persons[p];
    }
    // Sort the pairs[] array
    sort(pairs, pairs + N);
    // Calculate the temporary positions and check for validity
    for (int p = 0; p < N; p++) {
        int temp = p - pairs[p].first;
        // Not possible to create the original queue.
        if (temp < 0) {
            cout << "It is not possible to create the original queue" << endl;
            return;
        }
        res[p] = temp;
    }
    // Update the temporary positions to handle multiple people with the same number of taller people in front
    for (int p = 0; p < N; p++) {
        for (int q = 0; q < p; q++) {
            if (res[q] >= res[p])
                res[q]++;
        }
    }
    cout << "The original queue is " << endl;
    for (int p = 0; p < N; p++) {
        cout << pairs[p].second << " " << res[p] + 1 << endl;
    }
}
int main() {
    int N = 4;
    // Person names
    string persons[N] = {"pq", "rs", "tu", "vw"};
    // Number of taller people
    int nums[N] = {0, 1, 0, 0};
    FindOriginalQueue(persons, nums, N);
    return 0;
}

輸出

原始佇列是

pq 1
tu 2
vw 4
rs 3

時間複雜度 - 遍歷 ‘res’ 陣列為 O(N*N)。

空間複雜度 - 在 pairs 陣列中儲存陣列元素為 O(N)。