首页 > 代码库 > 洛谷 1908逆序对
洛谷 1908逆序对
P1908 逆序对
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入输出格式
输入格式:
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。
输出格式:
给定序列中逆序对的数目。
输入输出样例
输入样例#1:
6 5 4 2 6 3 1
输出样例#1:
11
说明
对于50%的数据,n≤2500
对于100%的数据,n≤40000。
思路:对于l~m中的任何一个x来说,所有在m+1~r中的<x的数都在x的后面,所以分别将l~m和m+1~r进行排序不会改变逆序对的数目
代码:
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,ans; 5 int a[40001],b[40001]; 6 void merge_sort(int l,int r)//归并排序 7 { 8 if(l==r)return; 9 int m=(l+r)/2; 10 merge_sort(l,m); 11 merge_sort(m+1,r); 12 int i=l,j=m+1,k=l; 13 while(i<=m && j<=r) 14 if(a[i]<=a[j])b[k++]=a[i++]; 15 else ans+=m-i+1,b[k++]=a[j++];//若a[i]<a[j],则累加逆序对数 16 while(i<=m)b[k++]=a[i++];//合并 17 while(j<=r)b[k++]=a[j++]; 18 for(int i=l;i<=r;i++) 19 a[i]=b[i]; 20 } 21 int main() 22 { 23 cin>>n; 24 for(int i=1;i<=n;i++) 25 cin>>a[i]; 26 merge_sort(1,n); 27 cout<<ans; 28 return 0; 29 }
洛谷 1908逆序对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。