Sto provando a fare questo problema senza usare strutture dati particolari, sto dividendo l’array principale in 2 array diversi. Uno con solo gli elementi con indici pari, ed un altro con solo elementi di indice dispari. Ordino il primo array e con un piccolo algoritmo spiegato nel codice conto quanti swap ci sono voluti, stessa cosa per l’altro array e li sommo. Mi da molti risultati errati ma gli esempi giusti, avete consigli di input da testare per capire?
#include <vector>
#include <algorithm>
using namespace std;
bool possible(int V[], int N) {
for(int i = 0; i < N; ++i)
if(V[i] % 2 != i % 2)
return false;
return true;
}
long long minimum(vector<pair<int ,int>> V) {
long long ans = 0;
sort(V.begin(), V.end()); //prima sorto l'array
for(long long i = 0; i < V.size(); ++i) {
if(V[i].second == i) continue; //se la posizione iniziale e' uguale a quella di ora non e' stato scambiato
else {
swap(V[i], V[V[i].second]); //se invece la posizione e' cambiata,
// lo scambio con quello del suo vecchio indice e cosi' via, per una spiegazione migliore
// https://www.youtube.com/watch?v=-2_c4lG7k_M
++ans;
--i;
}
}
return ans;
}
long long paletta_sort(int N, int V[]) {
if(!possible(V, N)) //controllo se e' possibile ordinare l'array a paletta
return -1;
vector<pair<int, int>> V1;
vector<pair<int, int>> V2;
int ans = 0;
int cont0 = 0;
int cont1 = 0;
for(int i = 0; i < N; ++i) {
if(i % 2 == 0)
{V1.push_back({V[i], i-cont0}); ++cont0;}
else //divido l'array principale in 2 sottoarray con solo indici pari o con solo indici dispari
{V2.push_back({V[i], i-cont1-1}); ++cont1;}
}
return minimum(V1) + minimum(V2); //sommo gli scambi totali fatti
}
// grader
#include <iostream>
int main() {
int N;
cin>>N;
int V[N];
for(int i = 0; i < N; ++i) {
cin>>V[i];
}
cout << paletta_sort(N, V) << '\n';
return 0;
}