C++ 根据给定条件还原打乱的队列

在这个问题中，我们给出了每个人的姓名和站在他前面的较高人数。

我们可以根据每个人前面站着的较高人数来排序人们的位置。然后，我们根据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’前面有一个比他高的人。

输入

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;
}