Buongiorno. Sto provando questo problema delle nazionali dello scorso anno, ma riesco a completare solo un Subtask (il 4, N=K) mentre negli altri casi ci sono sempre 2/3 testcase errati, e quindi immagino di non aver considerato un caso da analizzare (o più di uno???)
La mia idea è quella di contare quante persone terminano la gara per ogni secondo, Q[n], limitandomi ad un massimo di K per secondo. Poi parto dall’ultimo secondo e torno indietro;
chiamo disp, il massimo delle persone che possono essere servite a partire dal secondo n, e utilizzo, se Q[n] >0,
R[n] = max(1+R[n+1], min(disp,Q[n]+R[n+1])));
per calcolare il risultato al secondo n.
Allego anche il codice:
vector cucina(int N, int K, int X, vector H){
vector Q;
vector R;
for (int i=0;i<X;i++) {
Q.push_back(0);
R.push_back(0);
}
for (int i=0;i<N;i++){
int h = H[i];
Q[h] +=1;
}
if (Q[X-1]>0) R[X-1] = 1;
for (int i=1;i<X;i++){
int n = X-1-i;
if (Q[n]>0) {
Q[n] = min(Q[n],K);
int disp = X-n;
R[n] = max(1+R[n+1],min(disp,Q[n]+R[n+1]));
}
else {
R[n] = R[n+1];
}
}
return R;
anche se disp è>=Q[n]+R[n+1]) non è detto che R[n] possa essere =Q[n]+R[n+1]) .
Uno dei Q[n] lo aggiungi subito gli altri vanno in coda e se in seguito la coda supera la lunghezza K?
Si, probabilmente l’errore potrebbe essere li.
Io pensavo di aver risolto il problema mettendo il minimo tra i secondi ancora disponibili (e quindi le persone servibili) e R[n+1] + Q[n], dove precedentemente Q[n] era già stato modificato con min(Q[n], K).
Probabilmente sbaglio proprio approccio.
Stavo facendo anche io questo problema, non riesco solo a capire come è possibile fare controlli sulla coda senza che la complessità degeneri in O(X^2).
Qualcuno a qualche indizio?
ovviamente partendo dal secondo 0 otterresti una soluzione troppo lenta. partendo invece dal fondo, potresti calcolare la risposta per X-1, e poi iterare all’indietro riutilizzando la risposta al secondo i+1, ottenendo quindi come complessità O(X)
Io ho risolto impostando una variabile coda=0 all’inizio e aggiungendo ad essa, per ogni secondo a partire da X-1 fino a 0, il numero di persone che finiscono la gara in quel secondo. Se la coda supera K, diminuisco il numero di persone che finiscono in quel momendo la gara, del numero necessario a fare in modo che la coda non superi K, e ovviamente diminuisco anche la coda. Calcolo la soluzione per quel secondo e poi, se la coda >0, la diminuisco di 1, perché una persona è stata servita. Passo poi al secondo precedente, fino a zero.
Non so se sono stato abbastanza chiaro…