首页 > > 程序设计 > C/C++ >

1688 求逆序对

2018-06-17 23:00:03来源：未知阅读 ()

1688 求逆序对

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目

数据范围：N<=10⁵。Ai<=10⁵。时间限制为1s。

输入描述 Input Description

第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。

输出描述 Output Description

所有逆序对总数.

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 long long int a[1000001];
 5 long long int tot;
 6 long long int n;
 7 long long int ans[1000001];//储存结果 
 8 long long int now;//表示已经有多少个结果 
 9 void f(long long int s,long long int t)
10 {
11     //int mid,i,j,k;
12     if(s==t)return;
13     int mid=(s+t)/2;
14     f(s,mid);
15     f(mid+1,t);
16     long long int i=s;
17     long long int j=mid+1;
18     now=s;
19     while(i<=mid&&j<=t)
20     {
21         if(a[i]<=a[j])
22         {
23             //tot++;
24         
25             ans[now]=a[i];
26             i++;
27             now++;
28         }
29         else
30         {    
31             tot=tot+mid-i+1;
32             ans[now]=a[j];
33             j++;
34             now++;
35         }
36     }
37     while(i<=mid)
38     {
39         ans[now]=a[i];
40         i++;
41         now++;
42     }
43     while(j<=t)
44     {
45         ans[now]=a[j];
46         j++;
47         now++;
48     }
49     for (i=s;i<=t;i++)//把合并后的有序数据重新放回a数组
50         a[i] = ans[i];
51 
52 }
53 int main()
54 {
55     long long int n;
56     cin>>n;
57     for(int i=1;i<=n;i++)
58         cin>>a[i];
59     f(1,n);
60     cout<<tot;
61     /*for(int i=1;i<=n;i++)
62     {
63         cout<<a[i]<<" ";
64     }*/
65     return 0;
66 }