URI (BEECROWD) - 1548 - Fila do Recreio - Estruturas e Bibliotecas - C e C++

Olá! Tem novidade no blog! Agora vamos resolver um problema da categoria "Estruturas e Bibliotecas" do URI/BEECROWD. Não é uma categoria que costumo resolver muitos problemas... mas aí vai! Confere mais abaixo no post!

Plataforma: URI (BEECROWD)

Problema: 1548

Enunciado:

Na escola onde você estuda, a hora do recreio é a mais aguardada pela grande maioria dos alunos. Não só porque as vezes as aulas são cansativas, mas sim porque a merenda servida é muito boa, preparada por um chefe italiano muito caprichoso. 

Quando bate o sinal para a hora do recreio, todos os alunos saem correndo da sua sala para chegar o mais cedo possível na cantina, tanta é a vontade de comer. Um de seus professores notou, porém, que havia ali uma oportunidade. Utilizando um sistema de recompensa, seu professor de matemática disse que a ordem da fila para se servir será dada não pela ordem de chegada, mas sim pela soma das notas obtidas em sala de aula. Assim, aqueles com maior nota poderão se servir antes daqueles que tem menor nota.

Sua tarefa é simples: dada a ordem de chegada dos alunos na cantina, e as suas respectivas notas na matéria de matemática, reordene a fila de acordo com as notas de matemática, e diga quantos alunos não precisaram trocar de lugar nessa reordenação.

Linguagens: C e C++

Solução:

Utilizar dois vetores ou arrays que, inicialmente zerados, devem receber os valores lidos. Um dos vetores permanece com os dados originais e o outro é ordenado. Por fim, percorre-se um dos vetores e compara-se os elementos dele, em cada posição, com os do outro vetor, contando a quantidade de valores que permanece em sua posição original. Por fim, basta imprimir o contador.

Código em C:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int compara(const void *a, const void *b) {
   return (*(int*)b - *(int*)a);
}

int main() {
    
    int n, m, i, resposta, valor, original[1000], ordenado[1000];
    scanf("%d", &n);
    
    while (n--) {
        
        scanf("%d", &m);
        memset(original, 0, sizeof original);
        memset(ordenado, 0, sizeof ordenado);
        
        for (i = 0; i < m; i++) {
            resposta = 0;
            scanf("%d", &valor);
            original[i] = valor;
            ordenado[i] = valor;
        }
        qsort(ordenado, m, sizeof(int), compara);
        
        for (i = 0; i < m; i++)
            if (ordenado[i] == original[i])
                resposta++;

        printf("%d\n", resposta);
    }
    return 0;
}

Código em C++:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    
    vector<int> original, ordenado;
    int n, m, i, resposta, valor;
    cin >> n;
    
    while (n--) {
        
        cin >> m;
        original.clear();
        ordenado.clear();
        
        while (m--) {
            resposta = 0;
            cin >> valor;
            original.push_back(valor);
            ordenado.push_back(valor);
        }
        sort(ordenado.begin(), ordenado.end(), greater<int>());
        
        for (i = 0; i < ordenado.size(); i++)
            if (ordenado.at(i) == original.at(i))
                resposta++;

        cout << resposta << endl;
    }
    return 0;
}