Ciao a tutti, sto cercando di risolvere questo esercizio senza una struttura dati troppo complicata, divido l’array in due parti e ordino ogni parte con un semplice bubble sort che mi permette di contare gli scambi, suggerimenti?
#include <vector>
#include <iostream>
using namespace std;
long long paletta_sort(int N, int V[])
{
int n1, n2, count=0;
vector <int> pari, dispari;
if (N%2==0)
{
pari.resize(N/2);
dispari.resize(N/2);
n1=N/2;
n2=N/2;
}
else
{
pari.resize(N/2+1);
dispari.resize(N/2);
n1=N/2+1;
n2=N/2;
}
for (int i=0; i<N; i++)
{
if (i%2==0)
{
pari[i/2]=V[i];
if (V[i]%2!=0)
return -1;
}
else
{
dispari[i/2]=V[i];
if (V[i]%2==0)
return -1;
}
}
int n=n1, s;
while (n-1>0)
{
for (int i=0; i<n-1; i++)
{
if (pari[i]>pari[i+1])
{
s=pari[i];
pari[i]=pari[i+1];
pari[i+1]=s;
count++;
}
}
n--;
}
n=n2;
while (n-1>0)
{
for (int i=0; i<n-1; i++)
{
if (dispari[i]>dispari[i+1])
{
s=dispari[i];
dispari[i]=dispari[i+1];
dispari[i+1]=s;
count++;
}
}
n--;
}
return count;
}
Ciao, anche se l’idea è corretta, non ti puoi permettere di eseguire effettivamente il bubblesort perché ottieni un algoritmo con complessità O(N^2), troppo elevata per questo problema. Quindi devi riuscire a contare il numero si scambi che il bubblesort esegue, ma in modo più efficiente. Per prima cosa si può dimostrare che questo numero è uguale al numero di inversioni nell’array, per esempio nell’array [ 1, 5, 2, 3, 4 ] ci sono 3 coppie invertite che sono (5,2), (5,3) e (5,4), e quindi il bubblesort farà 3 scambi.
Ci sono in realtà diversi modi per contare le inversioni in un array, dal mio punto di vista il più semplice è scorrere l’array al contrario e usare un fenwick tree per tenere traccia degli elementi incontrati e sapere velocemente quanti ce ne sono più piccoli di x (oppure potresti usare un segment tree, forse passa con il nuovo server, ma non sono sicuro, in teoria in gara non doveva passare), non so se rientri nella tua classificazione di struttura troppo complicata. Altrimenti un’alternativa è il mergesort. In ogni caso di tutti questi metodi puoi trovare delle ottime spiegazioni online (e suppongo anche sul forum stesso (?)).
Adesso non ricordo bene tutte le funzionalità che offrono, ma credo sia possibile una soluzione con i set delle pbds, ma fossi in te non mi addentrerei in questa strada (e per giunta non so neanche se sarebbe abbastanza veloce).
Grazie mille, in realtà ho migliorato un po’ il codice ottenendo 70 punti. Vedo se riesco a trovare qualcosa alla mia portata, il segment tree ho provato a studiarlo ma mi sembra troppo complesso