Openjudge 求排列的逆序数

求排列的逆序数
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1,i2,…,in,如果其中存在j,k,满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。显然,由1,2,…,n 构成的所有n!个排列中,最小的逆序数是0,对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列,求它的逆序数。

输入
第一行是一个整数n,表示该排列有n个数(n <= 100000)。 第二行是n个不同的正整数,之间以空格隔开,表示该排列。 输出 输出该排列的逆序数。 样例输入 6 2 6 3 4 5 1 样例输出 8 提示 1. 利用二分归并排序算法(分治); 2. 注意结果可能超过int的范围,需要用long long存储。 来源 习题(15-4)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
using namespace std;
/*
void print(int *a,int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
*/

void Merge(int *a,int s,int m,int e,int *b){
    int ptr1=s,ptr2=m+1,ptr=s;
    while (ptr1<=m&&ptr2<=e){
        if (a[ptr1]>a[ptr2]) b[ptr++]=a[ptr1++];
        else b[ptr++]=a[ptr2++];
    }
    while (ptr1<=m){
        b[ptr++]=a[ptr1++];
    }
    while (ptr2<=e){
        b[ptr++]=a[ptr2++];
    }
    for(int i=s;i<=e;i++){
        a[i]=b[i];
    }
}
long long getN(int *a,int s,int m,int e){
    //if(s>=m)return 0;
    long long re=0;
    int ptr1=s,ptr2=m+1;
    while(ptr1<=m&&ptr2<=e){
        if(a[ptr1]>a[ptr2]){
            re+=e-ptr2+1;
            //print(a+s,e-s+1);
            //cout<<a[ptr1]<<" "<<a[ptr2]<<" "<<re<<endl;
            ptr1++;
        }else{
            ptr2++;
        }
    }
    return re;
}
long long MergeSort(int *a,int s,int e,int *b){
    if(s<e){
        long long total=0;
        int m=s+(e-s)/2;
        total+=MergeSort(a,s,m,b);
        total+=MergeSort(a,m+1,e,b);
        total+=getN(a,s,m,e);
        Merge(a,s,m,e,b);
        return total;
    }
    return 0;
}
int main(){
    int n;
    cin>>n;
    int * array=new int[n];
    int * array2=new int[n];
    for(int i=0;i<n;i++){
        cin>>array[i];
    }
    long long re=MergeSort(array,0,n-1,array2);
    cout<<re;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注