Non riesco a superare i 70/100 in questo problema, per limitare l’uso della RAM nell’ultimo subtask ho usato una map e per evitare i timeout una ricerca binaria alla fine, però non riesco a capire come fare.
Questo è il codice:
Grazie.
Devi cercare di trovare una soluzione con complessità O(N), dovrebbe facilitarti sapere che i valori in input sono già in ordine crescente 
Ho provato un altro algoritmo, funziona così:
- necessari = 1 (carica necessaria per poter raggiungere la fine)
- carica = 1 (variabile che contiene la carica del cellulare)
- ultima_posizione = 1 (istante di tempo in cui ho la carica specificata in “carica”)
- Per ogni intervallo di ricarica:
-
- Calcola quanti punti perde il telefono di carica (A[i] - ultima_posizione)
-
- Se la carica attuale non basta per raggiungere l’inizio partendo da ultima_posizione, aumenta la variabile “necessari” del numero di punti di carica necessaria e togli dalla variabile carica ilo stesso numero di punti
-
- Aumenta carica del valore A[i]-B[i]+1 (cioè la lunghezza del periodo di ricarica)
- Ritorna la variabile necessari
Codice: http://pastebin.com/2fV6eZam
Qualche consiglio? Ottengo 10/100, quasi tutti output errato.
L’idea mi sembra corretta e rispetta i limiti di tempo posti dal problema
L’unica cosa a cui dovresti però fare attenzione è che l’ultimo intervallo potrebbe finire prima di M e quindi ti potrebbe rimanere del tempo “scoperto” da considerare
EDIT: Inoltre, c’è anche un errore nel modo in cui consideri la carica rimasta nel cellulare. Non devi togliere quella che aggiungi quando ti accorgi che te ne serviva di più alla partenza, la parte necessaria l’hai già sottratta quando hai calcolato la differenza con l’intervallo precedente.
Mettendo insieme le due correzioni dovresti totalizzare un punteggio pieno
Ho riscritto l’algoritmo con un’idea diversa, in pratica di calcolare quale fosse la carica minima raggiunta, tuttavia i tuoi consigli (sul tempo scoperto) mi sono stati utili.
Grazie, sono riuscito a fare 100/100