Buon pomeriggio,
sto cercando di risolvere il problema treni: CMSocial - a social coding app e ho scritto un codice che però risolve solo i subtask 1,2 e 3.
La soluzione si basa sullo scorrere lungo gli array a e b e considerare di volta in volta una riga, controllando anche le due precedenti. L’algoritmo valuta se è meglio prendere il treno a o il treno b (eliminando in questo caso la scelta fatta alla riga precedente), raggiungendo quindi di volta in volta la soluzione ottima per quella data riga. Il codice risolve correttamente i primi 3 subtask ma poi restituisce “output incorrect” per tutti i test del 4 e del 5.
int tempo_massimo(int N, int a[], int b[])
{
long long tot = 0; //durata totale aumentata progressivamente
long long preadd = 0; //valore aggiunto alla riga precedente
long long prepreadd = 0; //valore aggiunto due righe prima
for(int i = 0; i < N; i++){
if(i == 0){ //alla prima riga considero semplicemente il treno di durata maggiore
if (a[i] > b[i]){
tot += a[i];
preadd = a[i];
}
else{
tot += b[i];
preadd = b[i];
}
//cout << tot << " "<< preadd << " " << prepreadd << endl;
}
else if(i == 1){ //alla seconda riga valuto se è maggiore:
if((b[i] - preadd) > a[i]){ //1) inserire il valore di b ed eliminare quello inserito alla riga prima
tot += (b[i] - preadd);
prepreadd = 0;
preadd = b[i];
}else{ //2) inserire solo il valore di a
tot += a[i];
prepreadd = preadd;
preadd = a[i];
}
//cout << tot << " "<< preadd << " " << prepreadd << endl;
}
else{ //dalla terza riga in poi faccio la stessa cosa che con la seconda ma con un controllo ulteriore su "prepreadd"
long long primoterm = 0;
if(prepreadd == 0){ //se due righe prima non avevo preso nessun treno (per prendere alla riga prima il treno b),
//dato che ora cambio la riga prima per non prendere nessun treno non ho più bisogno di lasciare vuoto due righe prima
//e posso cambiarlo per prendere il treno a
primoterm = b[i] - preadd + a[i-2];
}else{
primoterm = b[i] - preadd;
}
if (primoterm >= a[i]){ //controllo se mi conviene prendere b (con la condizione che ne deriva) oppure a
tot += primoterm;
prepreadd = 0; //aggiorno già coi valori che userò al prossimo ciclo
preadd = b[i];
}else{
tot += a[i];
prepreadd = preadd;
preadd = a[i];
}
//cout << tot << " "<< preadd << " " << prepreadd << endl;
}
}
return tot;
}
Provo a pensare un nuovo algoritmo!