TÓPICO

Porque eu recebo limite de tempo excedido

Montivero-Josias-UTN FRSF 2017 - AEDD -B perguntou 2 anos atrás

#include <iostream>
using namespace std;

int buscarCanicas(int C[], int, int);
void leerNCanicas(int C[], int);
void ordenarNCanicas(int C[], int);

int main() {
    int NCanicas, QPreguntas, pruebasCont=1;
    while((cin >> NCanicas >> QPreguntas) && (NCanicas && QPreguntas) )
    {
        int Canicas[NCanicas+1];
        leerNCanicas(Canicas, NCanicas);
        ordenarNCanicas(Canicas, NCanicas);

        cout << "CASE# " << pruebasCont << ":" << endl;
        for(int i = 0; i < QPreguntas; i++) {
            int consultaCanica;
            cin >> consultaCanica;

            int posCanica = buscarCanicas(Canicas, NCanicas, consultaCanica);

            if(posCanica == -1)
                cout << consultaCanica << " not found" << endl;
            else
                cout << consultaCanica << " found at " << posCanica+1 << endl;
        }
        cin >> NCanicas >> QPreguntas;
        pruebasCont++;
    }
    return 0;
}

void leerNCanicas(int Canicas[], int TL) {
    for(int i = 0; i < TL; i++) 
        cin >> Canicas[i];
}

void ordenarNCanicas(int Canicas[], int TL) {
    for(int i = TL-1; i > 0; i--) 
        for(int j = 0; j < i; j++) 
            if(Canicas[j] > Canicas[j+1])
                swap(Canicas[j], Canicas[j+1]);
}

int buscarCanicas(int Canicas[], int TL, int Canica) {
    int MD;
    bool encontrado=false;

    int i = 0;
    while(i < TL && !encontrado) {

        if(Canica == Canicas[i]) {
            encontrado = true;
            MD = i;
        }
        i++;
    }

    return (encontrado ? MD : -1);
}

Preciso de ajuda rápida

Lembre de não publicar soluções. Sua publicação pode ser revisada por nossos moderadores.

  • Vitor Vilela respondido 1 ano atrás

    Além da ordenação que é O(n²) e pode ser otimizada pra O(n log n), que é muito mais rápida, a função buscarCaninas é O(n) pois ela sempre poderá navegar o vetor inteiro. Usando um conceito chamado busca binária você pode otimizar essa função pra O(log n), já que para um vetor ordenado você pode ir começando a busca pelo "centro" do vetor e ir indo pra metade da esquerda ou direita recursivamente até chegar no valor encontrado, que é muito mais rápido.

  • Jacques Brancher respondido 1 ano atrás

    Estou com o mesmo problema. Sugestão: Troque a ordenação para quicksort (é o primeiro passo).