1228 - Grid de Largada

Como tem no máximo 24 carros, InsertionSort pode resolver o problema!

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Como estamos tratando de ultrapassagens, então o algoritmo de ordenação InsertionSort consegue caracterizar muito bem a simulação que precisaremos fazer. A grande diferença entre uma ordenação normal e a ordenação que precisamos fazer aqui é que nosso objetivo não é colocar todos os elementos na ordem crescente, e sim colocar na ordem dos carros ao final da corrida. Podemos fazer isso guardando a informação de cada posição de cada elemento ao final e usar esta posição desejada como parâmetro de comparação.

C99

#include <stdio.h>

int pos_final[25];

int comp(int a, int b)
{
    return pos_final[a] - pos_final[b];
}

void swap(int *a, int *b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

int insertionSort(int *V, int n)
{
    int inversoes = 0;

    for (int i = 1; i < n; ++i)
    {
        int j = i, k = j - 1;

        while (k > -1 && comp(V[j], V[k]) < 0)
        {
            swap(&V[j], &V[k]);
            ++inversoes;
            --j, --k;
        }
    }

    return inversoes;
}

int main()
{
    int N, comeco[24], final[24];

    while (scanf("%d", &N) != EOF)
    {
        for (int i = 0; i < N; ++i)
        {
            scanf("%d", &comeco[i]);
        }

        for (int i = 0; i < N; ++i)
        {
            scanf("%d", &final[i]);
            pos_final[final[i]] = i;
        }

        printf("%d\n", insertionSort(comeco, N));
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9