il mio codice da fuori tempo all’ultimo tast case, come faccio a renderlo più veloce? #include <fstream>#include <vector>#include <algorithm>using namespace std - Pastebin.com
Effettivamente il tuo l’algoritmo ha una complessità troppo elevata, ovvero O(n^2).
Per aiutarti a capire come migliorarlo ti presento due input.
Input 1:
3
1 4
2 5
3 6
Input 2:
3
1 6
2 4
3 5
Quali sono le risposte per questi due casi?
1 Mi Piace
dovrebbe essere per entrambi i casi 6, nel primo caso il tutor 1 offre al tutor 0 e il tutor 2 offre ai primi due, nel secondo caso idem, penso perché l’ultimo arriva prima che uno se ne vada
Esattamente, quindi a te basterebbe sapere che:
Le entrate avvengono ai momenti
1, 2, 3
(non serve sapere quale tutor entra all’istante 1, quale all’istante 2 e quale al 3)
Le uscite avvengono ai momenti
4, 5, 6
(come prima non serve sapere esattamente l’istante di uscita di ogni tutor, ma basta conoscere la lista di questi istanti)
Basandoti solo su queste informazioni, sapresti determinare la risposta, ovvero 6.
Prova ad esempio a trovare la risposta per questo caso (con N = 4):
Le entrate avvengono ai momenti
1, 3, 6, 10
Le uscite avvengono ai momenti
4, 7, 11, 12
1 Mi Piace
potrei vedere quanti tutor ci sono ogni istante e ogni volta che entra uno nuovo aggiungo alla somma
Esattamente, ora puoi applicare questo ragionamento anche al tipo di input originale (dato che riesci a calcolarti le due liste di istanti). Per implementarlo dovrebbe bastare un sort e un ciclo for, con una complessità totale di O(N\times log(N))
1 Mi Piace
100/100, grazie mille, da appuntare che non c’è bisogno di creare un array con tutte le posizioni possibili, ma basta crearlo grande 2*N, in modo da aggiungere ogni volta la posizione precedente e sommare o togliere 1 in base al momento in cui mi trovo(se ho che i tutor arrivano a 1, 3, 5 e se ne vanno a 6, 4, 7 allora alla prima posizione dell’array metterò un +1 e dalla seconda, in base a quale numero è più grande metterò +1 o meno 1, quindi alla seconda avrò 1+1, alla terza 2-1 etc.)
1 Mi Piace