Restaurar una cola mezclada según las condiciones dadas

Dadas N personas en una cola y dos arrays A[] y B[] . La array A[] representa el nombre de la persona y la array B[] representa cuántas personas son más altas que una persona en particular parada frente a ella. Ahora la cola se baraja. La tarea es imprimir la secuencia original de la cola siguiendo la propiedad anterior.

Ejemplos:

Entrada: N = 4, A[] = {‘a’, ‘b’, ‘c’, ‘d’}, B[] = {0, 2, 0, 0} 
Salida: 
a 1 
c 3 
d 4 
b 2 
Explicación: 
Mirando la cola de salida y sus alturas generadas, se puede entender fácilmente que: 
1) a es el primero en la cola, por lo que tenemos a la persona con el índice 0 delante de él. Entonces a está asociado con 0 en la entrada. 
2) c tiene solo a delante de él/ella pero a es más corta que c. Por lo tanto, c está asociado con 0 en la entrada. 
3) d tiene c y a delante de él/ella pero ambos son más cortos que d. Por lo tanto, d está asociado con 0 en la entrada. 
4) b tiene d, c y a delante de b. Pero solo c y d son más altos que b. Entonces, b está asociado con 2 en la entrada.

Entrada: N = 4, A[] = { ‘a’, ‘b’, ‘c’, ‘d’}, B[] = { 0, 1, 3, 3} 
Salida: -1 
Explicación: 
El orden dado es el orden original de la cola.

Acercarse:

• Primero haga un par del nombre de la persona y sus números enteros asociados y ordene los pares.
• Cree una respuesta de array [] para almacenar las posibles alturas de la persona.
• Iterar sobre todo el par y si el número de personas que están de pie delante es más alto y mayor que su posición de pie actual, entonces devuelve -1 .
• De lo contrario, almacene la diferencia entre la posición de pie actual y la altura de la persona más alta que él, en la array de respuesta.
• Para cada persona, itere sobre el par y si el valor de la array de respuesta para nuestra persona actual es mayor que la persona con la que estamos comparando , incremente en la array de respuesta para el par actual.
• Finalmente, imprima los posibles pares de la secuencia dada de acuerdo con los valores almacenados en la array answer[] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the Queue
void OriginalQueue(char A[], int B[],
                   int N)
{
    // Making a pair
    pair<int, string> a[N + 1];
 
    // Answer array
    int ans[N + 1];
    bool possible = true;
 
    // Store the values in the pair
    for (int i = 0; i < N; i++) {
        a[i].second = A[i];
        a[i].first = B[i];
    }
 
    // Sort the pair
    sort(a, a + N);
 
    // Traverse the pairs
    for (int i = 0; i < N; i++) {
 
        int len = i - a[i].first;
 
        // If it is not possible to
        // generate the Queue
        if (len < 0) {
 
            cout << "-1";
            possible = false;
        }
 
        if (!possible)
            break;
        else {
            ans[i] = len;
 
            for (int j = 0; j < i; j++) {
 
                // Increment the answer
                if (ans[j] >= ans[i])
                    ans[j]++;
            }
        }
 
        // Finally printing the answer
        if (i == N - 1 && possible) {
            for (int i = 0; i < N; i++) {
                cout << a[i].second << " "
                     << ans[i] + 1 << endl;
            }
        }
    }
}
 
// Driver Code
int main()
{
    int N = 4;
 
    // Given name of person as char
    char A[N] = { 'a', 'b', 'c', 'd' };
 
    // Associated integers
    int B[N] = { 0, 2, 0, 0 };
 
    // Function Call
    OriginalQueue(A, B, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.io.*;
 
class GFG{
     
// Function to generate the Queue
static void OriginalQueue(char A[], int B[],
                                    int N)
{
    // Making a pair
    int[][] a = new int[N][2];
 
    // Answer array
    int[] ans = new int[N];
    boolean possible = true;
 
    // Store the values in the pair
    for(int i = 0; i < N; i++)
    {
        a[i][0] = B[i];
        a[i][1] = (int)A[i];
    }
 
    // Sort the pair
    Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
     
    // Traverse the pairs
    for(int i = 0; i < N; i++)
    {
        int len = i - a[i][0];
 
        // If it is not possible to
        // generate the Queue
        if (len < 0)
        {
            System.out.print("-1");
            possible = false;
        }
 
        if (!possible)
            break;
        else
        {
            ans[i] = len;
 
            for(int j = 0; j < i; j++)
            {
 
                // Increment the answer
                if (ans[j] >= ans[i])
                    ans[j]++;
            }
        }
 
        // Finally printing the answer
        if (i == N - 1 && possible)
        {
            for(int k = 0; k < N; k++)
            {
                System.out.println((char)a[k][1] +
                                 " "+ (ans[k] + 1));
            }
        }
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 4;
     
    // Given name of person as char
    char A[] = { 'a', 'b', 'c', 'd' };
     
    // Associated integers
    int B[] = { 0, 2, 0, 0 };
     
    // Function Call
    OriginalQueue(A, B, N);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to generate the Queue
def OriginalQueue(A, B, N):
     
    # Making a pair
    a = [[0, ""] for i in range(N)]
 
    # Answer array
    ans = [0 for i in range(N)]
    possible = True
 
    # Store the values in the pair
    for i in range(N):
        a[i][1] = str(A[i])
        a[i][0] = B[i]
 
    # Sort the pair
    a.sort(reverse = False)
 
    # Traverse the pairs
    for i in range(N):
        len1 = i - a[i][0]
 
        # If it is not possible to
        # generate the Queue
        if (len1 < 0):
            print("-1",end = "")
            possible = False
 
        if (possible == False):
            break
        else:
            ans[i] = len1
 
            for j in range(i):
                 
                # Increment the answer
                if (ans[j] >= ans[i]):
                    ans[j] += 1
 
        # Finally printing the answer
        if (i == N - 1 and possible):
            for i in range(N):
                print(a[i][1], ans[i] + 1)
 
# Driver Code
if __name__ == '__main__':
     
    N = 4
 
    # Given name of person as char
    A = [ 'a', 'b', 'c', 'd' ]
 
    # Associated integers
    B = [ 0, 2, 0, 0 ]
 
    # Function Call
    OriginalQueue(A, B, N)
 
# This code is contributed by ipg2016107

<script>
 
// Javascript program for the above approach
 
// Function to generate the Queue
function OriginalQueue(A, B, N)
{
     
    // Making a pair
    var a = Array(N + 1);
    for(var i = 0; i < N; i++)
    {
        a[i] = [0, ""];
    }
 
    // Answer array
    var ans = Array(N + 1);
    var possible = true;
 
    // Store the values in the pair
    for(var i = 0; i < N; i++)
    {
        a[i][1] = A[i];
        a[i][0] = B[i];
    }
 
    // Sort the pair
    a.sort()
 
    // Traverse the pairs
    for(var i = 0; i < N; i++)
    {
        var len = i - a[i][0];
 
        // If it is not possible to
        // generate the Queue
        if (len < 0)
        {
            document.write("-1");
            possible = false;
        }
 
        if (!possible)
            break;
        else
        {
            ans[i] = len;
 
            for(var j = 0; j < i; j++)
            {
                 
                // Increment the answer
                if (ans[j] >= ans[i])
                    ans[j]++;
            }
        }
 
        // Finally printing the answer
        if (i == N - 1 && possible)
        {
            for(var i = 0; i < N; i++)
            {
                document.write(a[i][1] + " " +
                               (ans[i] + 1) + "<br>");
            }
        }
    }
}
 
// Driver Code
var N = 4;
 
// Given name of person as char
var A = [ 'a', 'b', 'c', 'd' ];
 
// Associated integers
var B = [ 0, 2, 0, 0 ];
 
// Function Call
OriginalQueue(A, B, N);
 
// This code is contributed by itsok
 
</script>

a 1
c 3
d 4
b 2

Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar: O(N)