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 
, fazemos a operação 
, e a quantidade de números maiores que que apareceram antes dele será 
(note que essas somas devem ser calculadas assim que é feita , pois estes resultados vão mudar depois).
Aqui, o código usando BIT:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |