Solução por Lucca Siaudzionis
Este problema é um problema clássico: contar o número de inversões para ordenar um array. Há várias formas de resolver este problema, algumas são:
- Insertion Sort
- Merge Sort
- BIT – Binary Indexed Tree (Árvore Indexada Binária), também conhecida como Fenwick Tree (Árvore de Fenwick)
Recomendamos o estudo dos três algoritmos, principalmente dos dois últimos. O mais poderoso dos três é o BIT, e um material muito bom de estudo dele (em inglês) pode ser visto aqui.
Com o BIT, resolvemos o problema contando, para cada número, quantos números maiores que ele aparecem antes dele no array e somando todos esses resultados. Para isso, toda vez que lermos um valor $$x$$, fazemos a operação $$insere(x)$$, e a quantidade de números maiores que $$x$$ que apareceram antes dele será $$somaate(\infty) – somaate(x)$$ (note que essas somas devem ser calculadas assim que é feita $$insere(x)$$, pois estes resultados vão mudar depois).
Aqui, o código usando BIT:
| #include <cstdio> | |
| #include <cstring> | |
| #define MAXN 100010 | |
| #define MAXS 1000010 | |
| #define max(A,B) (A)>(B)?(A):(B) | |
| int MAX = 1000001; | |
| int bit[MAXS]; | |
| void insere(int x){ | |
| while(x < 1000005){ | |
| bit[x]++; | |
| x += (x & -x); | |
| } | |
| } | |
| int soma_ate(int x){ | |
| int s = 0; | |
| while(x > 0){ | |
| s += bit[x]; | |
| x -= (x & -x); | |
| } | |
| return s; | |
| } | |
| int main(){ | |
| int n; | |
| memset(bit,0,sizeof bit); | |
| scanf("%d",&n); | |
| int resp=0; | |
| int hab[MAXN]; | |
| int maior=0; | |
| for(int i = 1;i<=n;i++){ | |
| scanf("%d",&hab[i]); | |
| maior = max(maior,hab[i]); | |
| } | |
| for(int i = 1;i<=n;i++){ | |
| insere(hab[i]); | |
| resp += soma_ate(maior) – soma_ate(hab[i]); | |
| } | |
| printf("%d\n",resp); | |
| return 0; | |
| } |
Aqui, o código usando Insertion Sort:
| #include <cstdio> | |
| #include <algorithm> | |
| #define MAXT 100005 | |
| using namespace std; | |
| int main(){ | |
| int n; | |
| scanf("%d",&n); | |
| int A[MAXT]; | |
| for(int i = 0;i<n;i++) scanf("%d",&A[i]); | |
| int resp=0; | |
| int B[MAXT]; | |
| int tamb = 0; | |
| B[0] = A[0]; | |
| for(int i = 0;i<n;i++){ | |
| tamb++; | |
| for(int j = tamb;j>=1;j–){ | |
| if(A[i] < B[j]){ | |
| B[j+1] = B[j]; | |
| resp++; | |
| } | |
| if(A[i] > B[j]){ | |
| B[j+1] = A[i]; | |
| break; | |
| } | |
| } | |
| } | |
| printf("%d\n",resp); | |
| return 0; | |
| } |
Comente