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语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:646 |
printf基础练习2 (C语言代码)浏览:567 |
人见人爱A+B (C语言代码)浏览:628 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:501 |
C语言训练-求函数值 (C语言代码)浏览:574 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:777 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:605 |
Minesweeper (C语言描述,蓝桥杯)浏览:1125 |
核桃的数量 (C语言代码)浏览:669 |
1124题解浏览:592 |