网站内容如何管理,成都犀牛网站建设,岱山建设网站,企业网站源码模板题目描述 对于数列a1,a2,a3…中的任意两个数ai,aj (i j)#xff0c;如果ai aj,那么我们就说这两个数构成了一个逆序对#xff1b;在一个数列中逆序对的总数称之为逆序数#xff0c;如数列 1 6 3 7 2 4 9中#xff0c;(6,4)是一个逆序对#xff0c;同样还有(3,2)… 题目描述 对于数列a1,a2,a3…中的任意两个数ai,aj (i j)如果ai aj,那么我们就说这两个数构成了一个逆序对在一个数列中逆序对的总数称之为逆序数如数列 1 6 3 7 2 4 9中(6,4)是一个逆序对同样还有(3,2),(7,4),(6,2)(6,3)等等你的任务是对给定的数列求出数列的逆序数。 输入 输入数据N(N 100000)表示数列中元素的个数随后输入N个正整数数字间以空格间隔。 输出 输出逆序数。 示例输入 10
10 9 8 7 6 5 4 3 2 1 示例输出 45 提示 /*归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid1,h]分别进行归并排序然后再将这两半合并起来。 在合并的过程中设limidmid1jh当a[i]a[j]时并不产生逆序数当a[i]a[j]时在 前半部分中比a[i]大的数都比a[j]大将a[j]放在a[i]前面的话逆序数要加上mid1-i。因此可以在归并 排序中的合并过程中计算逆序数.*/ #include iostream #includebits/stdc.h using namespace std; int tr[100001],sr[100001];//这里定义了一个暂时储存的数组和一个输入数组、 long int sum; void Merge(int s1,int e1,int s2,int e2) { int as1;//第一段序列的下标 int bs2;//第二段序列的下标 int c0;//暂存数组的下标 while(ae1be2)// 判断第一段和第二段取出的数哪个更小将其存入合并序列并继续向下遍历 { if(sr[a]sr[b]) tr[c]sr[a]; else { tr[c]sr[b]; sume1-a1; }//求逆序对(在有序序列中若a[i]a[j], 则a[i]后的元素皆大于a[j]) } while(ae1)// 若第一段序列还没遍历完将其剩余全部复制到合并序列 tr[c]sr[a]; while(be2)// 若第二段序列还没遍历完将其剩余全部复制到合并序列 tr[c]sr[b]; for(int is1;ie2;i)// 将合并序列复制到原始序列中 sr[i]tr[i-s1]; } void merge_sort(int s,int e) { int m; if(se) { m(se)/2; merge_sort(s,m);//左边有序 merge_sort(m1,e);//右边有序 Merge(s,m,m1,e);//合并两个有序序列注意起始位置 } } int main() { int n; sum0; scanf(%d,n); for(int i0;in;i) scanf(%d,sr[i]); merge_sort(0,n-1); printf(%ld\n,sum); return 0; }
