逆序数

逆序数

时间： 1ms        内存：128M

描述：

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如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

提示：

参考答案（内存最优[1392]）：

#include<stdio.h>
int sum=0;
void f1(int a[],int low,int mid,int high,int b[])
{
    int i=low,j=mid+1;
    int m=mid,n=high;
    int k=0;
     while (i<=m&&j<=n)
    {
        if (a[i]<=a[j])
            b[k++]=a[i++];
        else
        {
             b[k++]=a[j++];
             sum+=mid-i+1;
        }
    }
    while(i<=m)
        b[k++]=a[i++];
    while (j<=n)
        b[k++]=a[j++];
    for (i=0;i<k;i++)
        a[low+i]=b[i];
}
void f(int a[],int low,int high,int b[])
{
    int mid;
    if(low<high)
    {
        mid=low+(high-low)/2;
        f(a,low,mid,b);
        f(a,mid+1,high,b);
        f1(a,low,mid,high,b);
    }
}
int main()
{
    int n,i;
    int a[50001];
    int b[50001];
    memset(b,0,sizeof(b));
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        f(a,0,n-1,b);
    printf("%d\n",sum);
}

参考答案（时间最优[24]）：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 500005;
 
struct Node
{
	int val;
	int pos;
};
 
Node node[N];
int c[N], reflect[N], n;
 
bool cmp(const Node& a, const Node& b)
{
	return a.val < b.val;
}
 
int lowbit(int x)
{
	return x & (-x);
}
 
void update(int x)
{
	while (x <= n)
	{
		c[x] += 1;
		x += lowbit(x);
	}
}
 
int getsum(int x)
{
	int sum = 0;
	while (x > 0)
	{
		sum += c[x];
		x -= lowbit(x);
	}
	return sum;
}
 
int main()
{
	while (scanf("%d", &n) != EOF && n)
	{
		for (int i = 1; i <= n; ++i) 
		{
			scanf("%d", &node[i].val);
			node[i].pos = i;
		}
		sort(node + 1, node + n + 1, cmp);   //排序
		for (int i = 1; i <= n; ++i) reflect[node[i].pos] = i;   //离散化
		for (int i = 1; i <= n; ++i) c[i] = 0;   //初始化树状数组
		long long ans = 0;
		for (int i = 1; i <= n; ++i)
		{
			update(reflect[i]);
			ans += i - getsum(reflect[i]);
		}
		printf("%lld\n", ans);
	} 
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。