#include <iostream>
#include <deque>
using namespace std;
int main() {
long int n;
cin>>n;
long int cd[n],dd[n];
long int cnt=0;
deque<int>c;
deque<int>d;
for(int i=0;i<n;i++){
cin>>cd[i];
c.push_back(cd[i]);
}
for(int i=0;i<n;i++){
cin>>dd[i];
d.push_back(dd[i]);
}
long long unsigned int costo=0;
for(int i=0;i<n-1;i++){
if(c[cnt]<=c[cnt+1]){
d[cnt]+=d[cnt+1];
c.erase(c.begin()+cnt+1,c.begin()+cnt+2);
d.erase(d.begin()+cnt+1,d.begin()+cnt+2);
cnt--;
}
cnt++;
}
for(int i=0;i<d.size();i++){
costo+=c[i]*d[i];
}
cout<<costo;
}
Qualcuno riesce ad aiutarmi a risolvere il problema?
Una piccola precisazione visto che è il tuo primo commento. Se riesci quando metti il codice fa si che abbia o un minimo di commenti o che le variabili abbiano nomi intuitivi (c=costo e d=distanza okay ma se lo metti esplicito può aiutare a leggere e correggere), e l’altra cosa aggiusta l’indentazione se puoi.
Ma passando alla domanda. L’idea è fondamentalmente corretta. L’unico problema è che è abbastanza inefficiente. In sostanza se un benzinaio non è una buona scelta lo elimini dalla deque. Ora, ho letto online che ha complessità O(1) la rimozione, che è buono idealmente, però pare che sia abbastanza stretto coi tempi l’esercizio. L’idea è tentare di eliminare tutte le operazioni inutili. Se ci fai caso quello che fai è fare 4 cicli distinti che durano N(ossia fino a 1 milione).
Ho provato a giocare col codice ed è possibile mantenendo la struttura generale arrivare a 100 togliendo cose, e gestendo il “non prendo dei benzinai” in modo diverso. Comunque ci sono riuscito di poco, sottomettendo due volte lo stesso codice una volta usciva di tempo in 1,2 testcases e l’altra faceva 100.
Se vuoi c’è un approccio (che è come al tempo avevo risolto l’esercizio) che è un ciclo unico(oltre a quelli che prendono i dati), e toglie proprio la parte di memorizzarsi da quali benzinai ti fermi.
La cosa strana è che con la tua soluzione alcuni output sono sbagliati, non saprei perché ma ottimizzandola sono andati via, idk.
Soluzione non ancora ottimizzata al massimo, non leggerla a meno che non ti blocchi.
#include <iostream>
#include <deque>
using namespace std;
long int ok[1000001];
int main() {
long int n;
cin>>n;
long int c[n],d[n];
long int cnt=0;
for(int i=0;i<n;i++){
ok[i] = 1;
cin>>c[i];
}
for(int i=0;i<n;i++){
cin>>d[i];
}
long long unsigned int costo=0;
int last=0;
for(int i=1;i<n;i++){
if(c[last]<=c[i] && ok[i]==1){
d[last]+=d[i];
ok[i] = 0;
}else{
last = i;
}
}
for(int i=0;i<n;i++){
costo+=c[i]*d[i]*ok[i];
}
cout<<costo;
}