Paletta sort (senza strutture dati)

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;
}

ciao, con questo input
5
4 1 2 3 0
il tuo programma restituisce 1 ma il risultato corretto è 3

grazie

1 Mi Piace