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语言代码)浏览:2755 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:510 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:689 |
求圆的面积 (C语言代码)浏览:1662 |
字符逆序 (C语言代码)浏览:608 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:819 |
分糖果 (C语言代码)浏览:910 |
杨辉三角 (C语言代码)浏览:675 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:526 |
很简单,,题解1041:C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:584 |