Buongiorno a tutti. Sto provando a risolvere il problema Soste in autostrada (autogrill) da un po’ oramai ma per ora mi funzionano solo i primi 2 casi e 2 del secondo subtask.
Questo è il mio codice:
#include <set>
using namespace std;
set<int> AG;
void inizia() {
return;
}
void apri(long long p) {
AG.insert(p);
return;
}
void chiudi(long long p) {
AG.erase(p);
return;
}
long long chiedi(long long p) {
if(AG.empty())
return -1;
auto NearestPos = AG.lower_bound(p);
if(AG.size() == 1 || NearestPos == AG.end() || NearestPos == AG.begin())
return *NearestPos;
if (*NearestPos == p)
return *NearestPos;
long long leftNearest = *prev(NearestPos);
long long rightNearest = *NearestPos;
if (p - leftNearest >= rightNearest - p)
return rightNearest;
return leftNearest;
}
Qualcuno riesce a trovare l’errore?
Grazie in anticipo
Dovresti rivedere un po’ i casi degeneri:
Intanto, se NearestPos == AG.end()
non poi restituire quel valore perché non esiste.
Poi se AG.size() == 1
non è detto che quell’elemento sia puntato da NearestPos
(non è detto che sia \geq p)
Grazie, pensavo che AG.end() si riferisse all’ultimo elemento del set come avevo letto online, e che non sono ancora molto esperto con il C++, allora come posso vedere l’ultimo elemento del set?
Nei std::set
come anche in tutte la STL, .end()
punta alla posizione subito dopo l’ultimo elemento.
Se ad esempio hai un vector<int> A = {1,2,3,4}
, A.end()
punterà subito dopo il 4, quindi prev(A.end())
puterà al 4.
Esistono, e sono molto comodi, i reverse iterator.
A.rbegin()
punta a 4 e A.rend()
punta alla posizione subito prima di 1.
Nel tuo caso AG.rbegin()
punta all’ultimo elemento di AG
Ok, grazie mille, proverò con AG.rend()
#include <set>
using namespace std;
set<int> AG;
void inizia() {
return;
}
void apri(long long p) {
AG.insert(p);
return;
}
void chiudi(long long p) {
AG.erase(p);
return;
}
long long chiedi(long long p) {
if(AG.empty())
return -1;
auto NearestPos = AG.lower_bound(p);
if (NearestPos == AG.end())
return *AG.rbegin();
if (NearestPos == AG.begin())
return *NearestPos;
if(AG.size() == 1)
return *NearestPos;
if (*NearestPos == p)
return *NearestPos;
long long leftNearest = *prev(NearestPos);
long long rightNearest = *NearestPos;
if (p - leftNearest >= rightNearest - p)
return rightNearest;
return leftNearest;
}
Usando AG.rbegin() Va molto meglio ma ancora non li risolve tutti
Non capisco proprio cosa altro potrei fare
Grazie ancora per l’aiuto
Controlla il tipo di dato del set
2 Mi Piace
Non ci credo. Grazie mille!
Ora 100/100
1 Mi Piace