首页 > 代码库 > Codevs 1688 求逆序对
Codevs 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
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,a[100010]={0},b[100010]; 7 long long ans=0; 8 void ni(int l,int r) 9 {10 if(l==r) return;11 int mid=(l+r)/2;12 ni(l,mid);ni(mid+1,r);13 int i=l,j=mid+1,k=l;14 while(i<=mid&&j<=r)15 {16 if(a[i]>a[j])17 {18 b[k++]=a[j++];19 ans+=mid-i+1;20 }21 else{22 b[k++]=a[i++];23 }24 }25 while(i<=mid) b[k++]=a[i++];26 while(j<=r) b[k++]=a[j++];27 for(int w=l;w<=r;w++) a[w]=b[w];28 }29 int main()30 {31 scanf("%d",&n);32 for(int i=1;i<=n;i++)33 { scanf("%d",&a[i]); }34 ni(1,n);35 printf("%lld",ans);36 return 0;37 }
Codevs 1688 求逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。