C++ 中根据给定条件恢复被打乱的队列

2025 年 5 月 22 日 | 阅读 4 分钟

在本文中，我们将讨论如何在 C++ 中根据给定条件以及其算法和实现来恢复打乱的队列。

问题陈述

考虑两个数组，A[] 和 B[]，以及 N 个人在排队。个人姓名由数组 A[] 表示，站在其前面且比该个人高的人数由数组 B[] 表示。现在，队伍被重新排列。任务是打印队列的初始顺序，同时遵循上述属性。

算法

步骤 1： 创建一个名为 "pairs[]" 的数组，用于存储个人姓名及其分配号码的对。

步骤 2： 遍历 persons[] 和 nums[] 数组，将它们的值组合到 pairs 数组中。

步骤 3： 为了对 pairs[] 数组进行排序，使用 sort() 函数。

步骤 4： 此外，在此步骤中，我们定义“res”列表并开始遍历 pairs[] 数组。

步骤 5： 如果 p - pairs[p].first 小于 0，则打印 -1，因为无法获得原始队列。

步骤 6： 如果不是，则更新 res[p] 中的 temp 字段。

步骤 7： 当前，我们必须修改 res[q] 集合中个人的位置。输入 'res' 数组并开始探索它。

步骤 8： 使用嵌套循环从索引 0 到索引 q 遍历 res 数组。

步骤 9： 如果 res[q] 大于或等于 res[p]，则将 res[q] 增加 1。

步骤 10： 打印出每个人的位置。

输入： N = 4, A[] = {'a', 'b', 'c', 'd'}, B[] = {0, 2, 0, 0}

输出

a 1

c 3

d 4

b 2

观察输出队列以及生成它们的高度，很明显：

索引为 0 的人在 a 的前面，因为他是队伍中的第一个人。因此，在输入中，与 0 相关联。
只有 a 站在 c 的前面，但 a 比 c 矮。因此，在输入中，c 与 0 相关联。
尽管 c 和 a 都在 d 的前面，但 d 比他们都高。因此，在输入中，d 与 0 相关联。
d、c 和 a 都在 b 的前面。但是，只有 d 和 c 比 b 高。因此，在输入中，b 与 2 相关联。

示例 1

让我们举一个例子来说明如何在 C++ 中根据给定条件恢复打乱的队列。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// Function to restore the shuffled queue
void restoreShuffledQueue(char names[], int positions[], int size) {
    // Creating a pair to store names and positions
    pair<int, string> person[size];

    // Array to store the final order
    int finalOrder[size];
    bool isPossible = true;

    // Storing names and positions in the pair
    for (int i = 0; i < size; i++) {
        person[i].second = names[i];
        person[i].first = positions[i];
    }

    // Sorting the pair based on positions
    sort(person, person + size);

    // Traverse the pairs
    for (int i = 0; i < size; i++) {
        int newPosition = i - person[i].first;

        // If it is not possible to generate the Queue
        if (newPosition < 0) {
            cout << "-1";
            isPossible = false;
        }

        if (!isPossible)
            break;
        else {
            finalOrder[i] = newPosition;

            // Adjusting positions
            for (int j = 0; j < i; j++) {
                if (finalOrder[j] >= finalOrder[i])
                    finalOrder[j]++;
            }
        }

        // Finally printing the restored queue
        if (i == size - 1 && isPossible) {
            for (int i = 0; i < size; i++) {
                cout << person[i].second << " " << finalOrder[i] + 1 << endl;
            }
        }
    }
}

// Main Code
int main() {
    int size = 4;

    // Names of persons
    char names[size][20] = {"John", "Alice", "Bob", "Eve"};

    // Associated positions
    int positions[size] = {0, 2, 0, 0};

    // Function Call
    restoreShuffledQueue(*names, positions, size);
    return 0;
}   

输出

J 1
h 3
n 4
o 2

示例 2

让我们举一个例子来说明如何在 C++ 中根据给定条件恢复打乱的队列。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// Function to find the original queue
void restoreOriginalQueue(string names[], int tallerCount[], int size) {
    pair<int, string> pairs[size];
    int originalOrder[size];

    // Insert elements into pairs[] array
    for (int i = 0; i < size; i++) {
        pairs[i].first = tallerCount[i];
        pairs[i].second = names[i];
    }

    // Sort the pairs[] array
    sort(pairs, pairs + size);

    // Calculate the temporary positions and check for validity
    for (int i = 0; i < size; i++) {
        int temp = i - pairs[i].first;

        // Not possible to create the original queue
        if (temp < 0) {
            cout << "It is not possible to create the original queue" << endl;
            return;
        }

        originalOrder[i] = temp;
    }

    // Update the temporary positions to handle multiple people with the same number of taller people in front
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < i; j++) {
            if (originalOrder[j] >= originalOrder[i])
                originalOrder[j]++;
        }
    }

    // Printing the original queue
    cout << "The original queue is:" << endl;
    for (int i = 0; i < size; i++) {
        cout << pairs[i].second << " " << originalOrder[i] + 1 << endl;
    }
}

int main() {
    int size = 4;

    // Person names
    string names[size] = {"Harsha", "vardhan", "sham", "Ram"};

    // Number of taller people
    int tallerCount[size] = {0, 1, 0, 0};

    // Function Call
    restoreOriginalQueue(names, tallerCount, size);

    return 0;
}   

输出

The original queue is:
Harsha 1
Ram 2
sham 4
vardhan 3

下一主题腐烂橘子问题 (C++)

C++ 中根据给定条件恢复被打乱的队列

问题陈述

算法

示例 1

示例 2

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中根据给定条件恢复被打乱的队列

问题陈述

算法

示例 1

示例 2

相关帖子

C++ 中的 exit(1)

C++ 中检查一个数是否为毕达哥拉斯素数

C++ 中的粒子群优化

C++ 中两个重叠矩形的总面积

C++ 中找到射破所有气球所需的最少箭数

C++ 中打印皇冠图案的程序

C++ 中重新排列远程条形码

C++ 中的访问者设计模式

C++ 中 std::thread 和 OpenMP 的区别

C++ 中查找前 N 个 Iccanobif 数的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器