import java.util.Scanner; public class Main { static int[]a; static int[]temp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); a=new int[n]; temp=new int[n+1]; for (int i = 0; i < n; i++) a[i]=sc.nextInt(); long ans = mergeSort(a, 0, n-1); System.out.println(ans); } static long mergeSort(int []a, int left, int right) { //定义终止条件 if (left >= right) return 0; //求中间值 int mid = (left + right) >> 1; //不断进行递归,使得数组呈现有序递增 long count = mergeSort(a, left, mid) + mergeSort(a, mid + 1, right); //i为左数组下标,j为右数组下标,pos为临时数组下标 int i = left, j = mid + 1; int pos = 1; while (i <= mid && j <= right) { //如果a[i]<a[j],那么A[j]时右数组中第一个大于a[i]的元素,a在左右两数组是升序的, //那么从mid+1到j-1的元素都小于a[i],则a[i]逆序数为j-mid-i if (a[i] <= a[j]) { temp[pos] = a[i]; ++i; count += (j - mid) - 1; } else { temp[pos] = a[j]; ++j; } pos++; } //左数组是否全部遍历 for (int k = i; k <= mid; k++) { temp[pos++] = a[k]; count += (j - mid) - 1; } //右数组是否全部遍历 for (int k = j; k <= right; k++) temp[pos++] = a[k]; pos = 1; //复制数组 for (int k = left; k <= right; k++,pos++) { a[k] = temp[pos]; } return count; } }
0.0分
2 人评分
C语言训练-求矩阵的两对角线上的元素之和 (C语言代码)浏览:3394 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:732 |
震宇大神的杀毒软件 (C++代码)浏览:1116 |
剔除相关数 (C语言代码)浏览:1012 |
多输入输出练习1 (C语言代码)浏览:1181 |
母牛的故事 (C语言代码)浏览:921 |
简单的a+b (C语言代码)浏览:685 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:681 |
C二级辅导-公约公倍 (C语言代码)浏览:483 |