题目描述
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。
输入
第1行:N,N为序列的长度(n <= 50000)
第2行:序列中的元素(0 <= A[i] <= 10^9)
输出
输出逆序数
样例输入
4
2 4 3 1
样例输出
4
参考代码
#include <stdio.h>
#define _MAX 50001
long ans = 0;
void Merge(long *A, long *B, int first, int mid, int last)
{
int i = first, j = mid + 1;
int cur = first;
while (i <= mid && j <= last)
{
if (A[i] <= A[j])
{
B[cur++] = A[i++];
} else
{
B[cur++] = A[j++];
ans += mid - i + 1;
}
}
while (i <= mid)
{
B[cur++] = A[i++];
}
while (j <= last)
{
B[cur++] = A[j++];
}
}
void MSort(long *A, long *B, int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
MSort(B, A, first, mid);
MSort(B, A, mid + 1, last);
Merge(A, B, first, mid, last);
}
return ;
}
int main(int argc, const char * argv[])
{
int N, i = 1;
long A[_MAX];
long B[_MAX];
scanf("%d", &N);
for (; i <= N; i++)
{
scanf("%ld", &A[i]);
B[i] = A[i];
}
MSort(A, B, 1, N);
printf("%ldn", ans);
return 0;
}
解析
暂无