51 nod 1019 逆序数

1019 逆序数 

第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

输出逆序数

4
2
4
3
1

4

两层循环的暴力会超时 O（n^2）;

归并排序求逆序数

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 50005
int p[MAX],t[MAX],anti = 0;
void merge(int first,int last)
{
    int mid = (first + last) / 2;
    int i1 = 0,i2 = first,i3 = mid + 1;
    while(i2 <= mid && i3 <= last)
    {
        if(p[i2] > p[i3])
        {
            t[i1 ++] = p[i3 ++];
            anti += mid - i2 + 1;
        }
        else
        t[i1 ++] = p[i2 ++];
    }
    while(i2 <= mid)
        t[i1 ++] = p[i2 ++];
    while(i3 <= last)
        t[i1 ++] = p[i3 ++];
    i1 = first;
    i2 = 0;
    while(i2 < last - first + 1)
    p[i1 ++] = t[i2 ++];
}
void merge_sort(int first,int last)
{
    int mid;
    if(first < last)
    {
        mid = (first + last)/2;
        merge_sort(first,mid);
        merge_sort(mid + 1,last);
        merge(first,last);
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++)
        cin >> p[i];
    merge_sort(0,n - 1);
    cout << anti << endl;
    return 0;
}

最后

以上就是缓慢玫瑰为你收集整理的51 nod 1019 逆序数的全部内容，希望文章能够帮你解决51 nod 1019 逆序数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。