第四题代码，ac import java.util.Scanner; public class Netease4 { private static long count = 0; //辅助归并排序的数组 private static int[] helper; //用来存位置信息 private static int[] oldIndex; //类似于helper数组的问题辅助oldIndex数组的 private static int[] oldIndex2; /** * 跟归并求逆序对个数一样的思路，只是存储了每个数关于索引位置的信息来计算 * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; helper = new int[n]; oldIndex = new int[n]; oldIndex2 = new int[n]; for (int i = 0; i < n; i++) { nums[i] = sc.nextInt(); oldIndex[i] = i; oldIndex2[i] = i; } mergeSort(nums, 0, n - 1); System.out.print(count); } private static void mergeSort(int[] nums, int low, int high) { if (high - low == 1) { if (nums[low] > nums[high]) { count++; swap(nums, low, high); swap(oldIndex, low, high); swap(oldIndex2, low, high); } return; } if (high == low) { return; } int mid = low + (high - low) / 2; mergeSort(nums, low, mid); mergeSort(nums, mid + 1, high); int index1 = mid, index2 = high, i = high; for (i = high; i >= low; i--) { if (index1 < low || index2 < mid + 1) { break; } if (nums[index1] <= nums[index2]) { helper[i] = nums[index2]; oldIndex2[i] = oldIndex[index2]; index2--; }else { helper[i] = nums[index1]; for (int j = mid + 1; j <= index2; j++) { count += oldIndex[j] - oldIndex[index1]; } oldIndex2[i] = oldIndex[index1]; index1--; } } //如果哪边没用完 if (index1 >= low) { while (index1 >= low) { helper[i] = nums[index1]; index1--; i--; } }else { while (index2 >= mid + 1) { helper[i] = nums[index2]; oldIndex2[i] = oldIndex[index2]; index2--; i--; } } for (int j = low; j <= high; j++) { nums[j] = helper[j]; oldIndex[j] = oldIndex2[j]; } } private static void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; } } /* 5 2 3 4 2 5 5 3 1 4 2 5 5 3 2 4 1 5 9 3 1 4 2 5 2 6 7 8 */