Aggiungo il modulo della differenza tra curr e prev(la posizione del massimo precedente) alla distanza percorsa
Faccio diventare a[curr] negativo in modo che non sia più il massimo
Così però non riesco ad andare oltre i 70 punti, e non mi viene in mente un algoritmo più efficiente.
Forse potrei fare in modo che, invece che rendere il massimo negativo, nel ciclo successivo cerca il massimo tra tutti gli elementi tranne esso in modo tale che, al ciclo i, esegua n-1-i confronti, ma non riesco proprio a capire come implementare questa soluzione. (Forse con un vector? Ma poi come faccio con le posizioni…)
int n,curr;
cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
int prev=0,t=0;
for(int i=0;i<n;i++){
curr=distance(a,max_element(a,a+n));
t+=abs(curr-prev);
a[curr]=-1;
prev=curr;
}
cout<<t;
return 0;
Ad ogni esecuzione del ciclo utilizzi la funzione std::max_element che non è il massimo in termini di prestazioni, per conservare sia il valore che le posizioni dei pulsanti potresti usare una struttura dati con un pair oppure un array di struct (che alla fine è esattamente come ho fatto io, ma gli ultimi due testcase falliscono ).
Stai eseguendo N volte max_element (che impiega ogni volta O(N)). Quindi per ora il tuo algoritmo ha complessità computazionale N \cdot O(N) = O(N^2), che è troppo grande per risolvere l’ultimo subtask.
La tua proposta (oltre alla questione implementativa, non irrilevante) non migliorerebbe comunque la complessità, infatti:
$$ \sum_{i=0}^{N-1} N-1-i = \sum_{i=1}^{N-1} i = \frac{N \cdot (N-1)}{2}$$
Forse so come mai falliscono gli ultimi due testcase!
Capitava anche a me, ero disperata, finché il mio professore non mi ha suggerito di cambiare il tipo di dato della risposta.
Mi spiego meglio: salvi la risposta al problema in una variabile che presumo sia un int. Beh, per gli ultimi testcase la risposta invece è abbastanza grande: dovresti usare un long long int per ottenere 100/100
).