1162 - Organizador de Vagões

O método de ordenação descrito é idêntico ao InsertionSort!

Descrição

beecrowd Talent Cloudbeecrowd

Solução

O processo de ordenação descrito envolve fazer trocas entre dois elementos consecutivos até que todos os elementos estejam ordenados, o que é precisamos o processo de ordenação do InsertionSort. Logo, tudo o que precisamos fazer é contar o número que vezes que uma troca de posição entre elementos acontece no InsertionSort.

O processo de ordenação também pode descrever o BubbleSort, mas não testei se os resultados são equivalentes.

C99

#include <stdio.h>

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

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

int insertionSort(int *V, int n)
{
    int trocas = 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]);
            ++trocas;
            --j, --k;
        }
    }

    return trocas;
}

int main()
{
    int N, L, vagoes[50];

    scanf("%d", &N);

    for (int k = 0; k < N; ++k)
    {
        scanf("%d", &L);

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

        printf("Optimal train swapping takes %d swaps.\n", insertionSort(vagoes, L));
    }

    return 0;
}

C++17

JavaScript 12.18