逆序数

链接：https://www.nowcoder.com/acm/contest/77/A
来源：牛客网

逆序数

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2，那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述:

第一行有一个整数n(1 <= n <= 100000),  然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。

输出描述:

输出这个序列中的逆序数

示例1

输入

5
4 5 1 3 2

输出

7


4 4 1有2对

暴力超时代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[100005];
 6 int main()
 7 {
 8     int n;
 9     int i, j;
10     scanf("%d", &n);
11     for (i = 1; i <= n; i++)
12     {
13         scanf("%d", &a[i]);
14     }
15     long long s = 0;
16     for (i = 1; i <= n; i++)
17     {
18         for (j = i + 1; j <= n; j++)
19         {
20             if (a[i] > a[j])
21                 s++;
22         }
23     }
24     printf("%d
", s);
25     return 0;
26 }

View Code

AC代码

 1 #include <iostream>
 2 using namespace std;
 3 int  a[100005];//存储有多少比它大的数字在它之前
 4 int main()
 5 {
 6     int n, m, i, j, k;
 7     cin >> n;
 8     long long int sum = 0;
 9     for (i = 1; i <= n; i++)
10     {
11         scanf("%d", &m);
12         sum = sum + a[m];// 有多少比它大的数字在他之前，就要加上多少组
13         for (j = 0; j<m; j++)//在它之前的数字都+1
14         {
15             a[j]++;
16         }
17     }
18     cout << sum << endl;
19 }

归并排序

 1 #include <stdio.h> 
 2 #define max 1000001 
 3 long long a[max],b[max]; 
 4 long long count; 
 5 void Merge(long long a[], int start, int mid , int end)  //归并排序的合并部分 
 6 { 
 7     int i = start,j = mid + 1,k = start; 
 8     while(i <= mid&&j <= end) 
 9     { 
10         if(a[i] <= a[j]) 
11         { 
12             b[k++] = a[i++]; 
13         } 
14         else 
15         { 
16             count += j - k;//统计逆序数对 
17             b[k++] = a[j++]; 
18         } 
19     } 
20     while(i <= mid) 
21     { 
22         b[k++] = a[i++]; 
23     } 
24     while(j <= end) 
25     { 
26         b[k++] = a[j++]; 
27     } 
28     for(int i = start; i <= end; i++) 
29     { 
30         a[i] = b[i]; 
31     } 
32 } 
33    
34 void MergeSort(long long a[], int start, int end)  //归并排序 
35 { 
36     if(start < end) 
37     { 
38         int mid = (start + end)/2; 
39         MergeSort(a,start,mid);     // 将前半部分排序 
40         MergeSort(a,mid+1,end);     // 将后半部分排序 
41         Merge(a,start,mid,end);     // 合并前后两个部分 
42     } 
43 } 
44 int main(int argc, char const *argv[]) 
45 { 
46     int n=1,m; 
47        
48     while(n--) 
49     { 
50         scanf("%d",&m); 
51         count = 0; 
52         for(int i = 0; i < m; i++) 
53         { 
54             scanf("%d",a+i); 
55         } 
56         MergeSort(a,0,m-1); 
57         printf("%lld
",count); 
58     } 
59     return 0; 
60 }

View Code

一开始以为要查重：结果超内存

struct node
{
    int c, d;
    bool operator <(const node &o) const
    {
        if (c == o.c) return d < o.d;
        else return c < o.c;
    }
}x;
map<node, bool>m;


if (a[i] > a[j])
{
    x.c = a[i];
    x.d = a[j];
    if (!m[x])
    {
        m[x] = 1;
        s++;
    }
}