Ciao! Sto provando a risolvere Autogrill utilizzando i Set. Il programma sembra funzionare ma ci mette troppo tempo…
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
set<long long>s;
void inizia() {
return;
}
void apri(long long p) {
s.emplace(p);
return;
}
void chiudi(long long p) {
s.erase(p);
return;
}
long long chiedi(long long p) {
long long mini = 100000000000;
if(s.empty()){
return -1;
}else{
for (auto it : s)
mini = min(abs(p-it),mini);
}
if(s.count(p+mini)==0){
return p-mini;
}
else return p+mini;
}
Soluzioni?
Potresti spiegare l’idea dietro il codice?
“apri” e “chiudi” aggiungono o eliminano ‘p’ dal set.
in sostanza il set si riempie con i numeri dei vari autogrill. Quindi se ho ad esempio:
a 5
a 2
c 5
alla fine mi risulta che nel set c’è solo l’elemento ‘5’ (ovvero l’unico Autogrill aperto).
A questo punto, quando mi viene chiesto l’Autogrill più vicino faccio 2 step:
- Calcolare il numero nel set più vicino a ‘p’
- Decidere cosa stampare
Nello specifico:
Qui ovviamente controllo solamente se il set è vuoto (tutti gli Autogrill sono chiusi)
Nel caso ci sia anche solo un elemento, invece, mi calcolo la minima differenza tra ‘p’ e i numeri nel set; facciamo finta che il mio set sia: [2,4,7,15,60] e che ‘p’ sia 21. Questa parte di codice troverà che la differenza è 6 (quindi mini = 6).
il numero ‘p’ (nel nostro esempio 21) sarà più vicino a ‘p+mini’ (21+6=27) o ‘p-mini’ (21-6=15).
Il problema mi chiede di preferire il più grande, ma s.count(27) in questo caso è 0, perchè l’Autogrill 27 non c’è nel set, di conseguenza la rispsota sarà 15, ottenuta con ‘p-mini’:
Grazie perché l’hai spiegato veramente bene.
Naturalmente a farti andare fuori tempo è il codice nella funzione chiedi.
In particolare è necessario stare a controllare tutti i numeri nel set?
Hint
set-lower_bound
Dovrai però usare degli accorgimenti anche per trovare elementi di valore minore rispetto al tuo parametro all’interno del set (non esiste una funzione che lo faccia).
Se ti blocchi ti mando il codice che ho usato per risolverlo
1 Mi Piace
Grazie mille! Aggiornerò a riguardo =)
1 Mi Piace
Curiosità: che metodo hai usato?
Ho mantenuto quello stile, semplicemente aggiungendo il lower_bound(). Nel caso posso spiegarti meglio… ma non so come si mandano messaggi privati? Nel caso non fosse possibile lascio il mio Telegram Telegram: Contact @OhItsLu
1 Mi Piace