根据给定条件恢复洗牌队列

---

在这个问题中，我们给出了角色名称以及站在该角色前面更高的人数。

我们可以根据站在任何人前面更高的人数对人员的位置进行排序。之后，我们根据 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)。