Aiuto per Tieni aggiornato il catalogo (catalogo)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Tieni aggiornato il catalogo.

Ciao, il codice penso funzioni, ma è lento (va fuori tempo, Time limit exceeded)
C’è qualche modo per farlo più efficente? Penso ad un vettore o ad un array dinamico, ma non sono pratico in c++

Ecco il mio codice:


#include <list>
std::list<int> libri;

void aggiungi(long long int id) {
    libri.push_front(id);
}

void togli(long long int id) {
    for (auto it = libri.begin(); it != libri.end(); ++it){
        if(*it == id){
            libri.erase(it);
            break;
        }
    }
}

int conta(long long int id) {
    int count = 0;
    for (auto it = libri.begin(); it != libri.end(); ++it){
        if(*it == id){
            count++;
        }
    }
    return count;
}

Grazie mille in anticipo!

2

Ciao, la tua soluzione fa TLE perchè utilizzi funzioni come push_front() e erase() che sono temporalmente molto dispendiose:
Il push_front di un elemento davanti a una lista è un’operazione che non crea una nuova posizione 0, ma ti aggiunge una posizione alla fine della lista e shifta tutti gli elementi a destra di uno (lasciando così la prima posizione libera per poter ospitare l’elemento); ha quindi complessità temporale O(N).

L’erase funziona in modo simile, shiftando tutti gli elementi a destra di quello scelto di una posizione verso sinistra (sovrascrivendo quello scelto) e eliminando l’ultima posizione della lista (rimasta vuota).

soluzione

Per questo ti consiglio di ripensare la tua soluzione utilizzando le mappe al posto delle liste (questa soluzione consiste in pochissime righe di codice, se la provi cerca di non complicare troppo la logica).
Ti consiglio di associare il numero del libro con il numero di copie (map<int, int> mp).

3

Grazie mille, effettivamente facendo questo ho sistemato il codice!

Mando il codice se qualcuno volesse una mano:

#include <map>
std::map<long long int, int> libri;

void aggiungi(long long int id) {
    libri[id]++;
}

void togli(long long int id) {
    if(libri[id] > 0){
        libri[id]--;
        if(libri[id] == 0){
            libri.erase(id);
        }
    }
}

int conta(long long int id) {
    return libri[id];
}
4

Ti segnalo che su una lista concatenata erase e push_front hanno complessità costante.
Ovviamente a essere lenta resta la ricerca lineare.

5

Ok, grazie mille, lo terrò a mente, scusate tanto per il mio errore… :pensive:

1 Mi Piace