Created
June 9, 2015 02:32
-
-
Save rogerioagjr/a8ff895cad23a7ca7843 to your computer and use it in GitHub Desktop.
Linhas Cruzadas
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
// Linhas Cruzadas - F1PJ - OBI 2015 | |
// Rogério Júnior | |
// Complexidade: O(n*log(n)) | |
#include <cstdio> // scanf e printf | |
#define MAXN 100100 // defino o limite de n | |
typedef long long int lli; // defino o tipo lli como long long int | |
int n, vetor[MAXN], aux[MAXN]; // declaro as variáveis e vetores que vamos usar | |
lli merge_sort(int ini, int fim){ // declaro a função merge_sort, que agora retorna um int | |
if(ini==fim) return 0; // se o intervalo tiver um único elemento, ele não tem inversões | |
// caso o contrário, declaro a variável invers, que começa com a soma das inversões das duas metades | |
lli invers=merge_sort(ini, (ini+fim)/2) + merge_sort((ini+fim)/2+1, fim); // observe que chamei a recursão e ordenei as metades | |
int tam=0, j=(ini+fim)/2+1; // declaro tam e j, como feito no código anterior do merge_sort | |
for(int i=ini; i<=(ini+fim)/2; i++){ // para cada posição da metade da esquerda | |
while(j<=fim && vetor[j]<vetor[i]){ // procuro os elementos da metade da direita menores que i | |
// os adiciono ao vetor aux | |
aux[tam]=vetor[j]; | |
tam++; | |
j++; // passo para o próximo elemento | |
invers+=(ini+fim)/2-i+1; // e adicino o número de inversões em metades diferentes com o elemento j | |
} | |
// adiciono o elemento i | |
aux[tam]=vetor[i]; | |
tam++; | |
} | |
// adiciono o resto dos elementosda segunda metade | |
while(j<=fim){ | |
aux[tam]=vetor[j]; | |
tam++; | |
j++; | |
} | |
for(int i=ini; i<=fim; i++) vetor[i]=aux[i-ini]; // e troco os valores do vetor original pelos ordenados | |
return invers; // retorno o número de inversões calculado | |
} | |
int main(){ | |
scanf("%d", &n); // leio o valor de n | |
for(int i=1; i<=n; i++) scanf("%d", &vetor[i]); // leio os valores do vetor | |
printf("%lld\n", merge_sort(1, n)); // imprimo a quantidade de inversões do vetor | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment