1688 求逆序对
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目
数据范围:N<=105。Ai<=105。时间限制为1s。
输入描述 Input Description
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3
数据范围及提示 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 }