Pagini recente » Cod sursa (job #3260091) | Cod sursa (job #1588947) | Cod sursa (job #1561376) | Cod sursa (job #1517386) | Cod sursa (job #1934767)
#include <cstdio>
int N, input[10001];
int aux[10001];
char ch;
long long Merge(int sequence[], int left, int right){
long long inversions = 0;
int middle = (left + right) / 2;
int i = left;
int j = middle + 1;
int k = left;
while(i <= middle && j <= right){
if(sequence[i] <= sequence[j]){
aux[k++] = sequence[i++];
}else{
aux[k++] = sequence[j++];
inversions += middle - i + 1;
}
}
while(i <= middle){
aux[k++] = sequence[i++];
}
while(j <= right){
aux[k++] = sequence[j++];
}
for(k = left; k <= right; k++){
sequence[k] = aux[k];
}
return inversions;
}
long long Sort(int sequence[], int left, int right){
long long inversions = 0;
if(left < right){
int middle = (left + right) / 2;
inversions += Sort(sequence, left, middle);
inversions += Sort(sequence, middle + 1, right);
inversions += Merge(sequence, left, right);
}
return inversions;
}
int main(){
freopen("litere.in", "r", stdin);
freopen("litere.out", "w", stdout);
scanf("%d", &N); getchar();
for(int i = 1; i <= N; i++){
ch = getchar();
input[i] = ch;
}
printf("%d", Sort(input, 1, N));
return 0;
}