Ciao ragazzi, sono riuscito a fare 70/100 nel problema pausa caffè (ois 2016), fallendo nell’ultimo task per esecuzione fuori tempo. La mia soluzione, in effetti, non è molto efficiente. Come tag ho visto che c’è ricerca binaria, ma non capisco come applicarla al problema. Ci sarebbe qualcuno che mi può dare qualche aiutino? Grazie in anticipo.
Ciao,
non bisogna esattamente utilizzare la ricerca binaria (o almeno io non l’ho utilizzata).
Avrai certo notato che gli intervalli sono compresi tra 0 e 10^9, quello che devi fare è utilizzare una struttura dati in grado “compattare” gli intervalli, poi basta solo scorrerli in ordine.
In che senso “compattare” ?
Un array di dimensione 10^9 direi che occupa un po’ troppa memoria, tuttavia alcune di queste informazione non verranno mai utilizzate poiché N è al più 40000, quello a cui mi riferivo io era una std::map dove inserisci solo i valori che leggi in input.
2 Mi Piace
Grazie per il tuo aiuto, ma continuo a non capire.
A cosa dovrebbe servirmi una map?
In effetti mi sono accorto solo ora che gli intervalli sono compresi tra 0 e 10^6 e non 10^9 e quindi si poteva evitare di usare la map, comunque il ragionamento è uguale usando o no la map. Quello che interessa a noi è sapere all’istante t quante persone ci sono al caffè, per farlo utilizziamo una array o una map dove alla posizione i mettiamo un 1 se arriva una persona e un -1 se se ne va una persona, in questo modo scorrendo possiamo sapere quante persone ci sono in ogni istante.
3 Mi Piace
Mi hai fatto venire in mente un fenwick… che ne pensi?
Generalmente in questo tipo di problemi abbiamo tre possibili soluzioni:
- Brute force: update O(N), query O(1)
- Lazy: update O(1), query O(N)
- Fenwick: update O(logN), query O(logN)
In questo problema abbiamo N update all’inizio e un’unica query alla fine e non vedo il senso di usare un fenwick.
2 Mi Piace