Problema Gasoline 40/100

Aiuto
1 
#include <iostream>
#include <vector>
using namespace std;
int main(){
	freopen("input.txt","r",stdin);
  
   int n_staz; cin>>n_staz;
   vector<int>costo_benzina(n_staz,0);
	vector<int>km_rimasti(n_staz,0);
	
   int n_costo[n_staz], n_distanze[n_staz];
   
   for(int i=0;i<n_staz;i++){
      cin>>n_costo[i];
      costo_benzina[i]=n_costo[i];
   }
       
   for(int i=0;i<n_staz;i++){
      cin>>n_distanze[i];
      km_rimasti[i]=n_distanze[i]; 
   }
   
   for(int i=0;i<n_staz-1;i++){
      if(costo_benzina[i]<=costo_benzina[i+1]){
        costo_benzina.erase(costo_benzina.begin()+i+1);
        km_rimasti[i]+=km_rimasti[i+1];
        km_rimasti.erase(km_rimasti.begin()+i+1);
        i--;
        n_staz--;
        
      }
   }
   int tot=0;
   for(int i=0;i<n_staz;i++){
      tot+=costo_benzina[i]*km_rimasti[i];
   }
   cout<<tot;
}

Con questo codice non riesco ad andare oltre il 40/100. Potreste darmi una mano a capire dove fallisce?

2

Questa porzione di codice ha complessità temporale pari a O(N^2).
Dovresti trovare un modo per evitare la seguente operazione:

1 Mi Piace
3 
#include <iostream>
using namespace std;
int main(){
	freopen("input.txt","r",stdin);
  
  long int n_staz; cin>>n_staz;
  long  int costo_benzina[n_staz];
  long int km_rimasti[n_staz];
	
	long int costo_benzina_finale[n_staz];
	long int km_rimasti_finale[n_staz];
 
     long int n_costo[n_staz], n_distanze[n_staz];
   
   for(int i=0;i<n_staz;i++){
      cin>>n_costo[i];
      costo_benzina[i]=n_costo[i];
   }
       
   for(int i=0;i<n_staz;i++){
      cin>>n_distanze[i];
      km_rimasti[i]=n_distanze[i]; 
   }
    long int cnt=0;
    long int tot=0;
   for(int i=0;i<n_staz;i++){ 
if(costo_benzina[i]>costo_benzina[i+1]){
         costo_benzina_finale[cnt]=costo_benzina[i];           
km_rimasti_finale[cnt]=km_rimasti[i];                         
   tot+=costo_benzina_finale[cnt]*km_rimasti_finale[cnt];
         cnt++;
      }else if(costo_benzina[i]<=costo_benzina[i+1]){
        costo_benzina[i+1]=costo_benzina[i];
        km_rimasti[i+1]+=km_rimasti[i];   
      }
         
      
   }
   cout<<tot;
}

Ho provato così ma restituisce sempre 40/100

4

Secondo me trovare un’idea più lineare ti può aiutare parecchio anche nell’implementazione: supponi di essere alla stazione i che ha come prezzo per la benzina p_i e devi arrivare alla stazione i + 1 ma non hai più benzina nel serbatoio, ora puoi pensare di avere 2 opzioni:

  1. Effettivamente mi conviene comprare la benzina in questa stazione.
  2. Mi conveniva prendere la benzina per arrivare alla prossima stazione in una delle stazione precedenti perché mi costava meno.

Pensandola in questo modo sembra più semplice raggiungere un algoritmo molto lineare.