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
Non ci credo. Grazie mille!
Ora 100/100