下标
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] arr = new int[n][2]; for(int i=0;i<n;i++){ arr[i][0] = sc.nextInt(); arr[i][1] = i; } long res = getAns(arr,n); System.out.println(res); } public static long getAns(int[][] arr,int n){ int[][] tmp = new int[n][2]; return reverse(arr,0,n-1,tmp); } public static long reverse(int[][] arr,int left,int right,int[][] tmp){ if(left>=right) return 0; int mid = (left+right)>>>1; long leftDistance = reverse(arr,left,mid,tmp); long rightDistance = reverse(arr,mid+1,right,tmp); if(arr[mid][0]<=arr[mid+1][0]) return leftDistance+rightDistance; long crossDistance = reverseCross(arr,left,mid,right,tmp); return crossDistance+leftDistance+rightDistance; } public static long reverseCross(int[][] arr,int left,int mid,int right,int[][] tmp){ for(int i=left;i<=right;i++){ tmp[i][0] = arr[i][0]; tmp[i][1] = arr[i][1]; } int i = left,j = mid+1; long count = 0; for(int k=left;k<=right;k++){ if(i==mid+1){ arr[k][0] = tmp[j][0]; arr[k][1] = tmp[j][1]; j++; }else if(j==right+1){ arr[k][0] = tmp[i][0]; arr[k][1] = tmp[i][1]; i++; }else if(tmp[i][0]<=tmp[j][0]){ arr[k][0] = tmp[i][0]; arr[k][1] = tmp[i][1]; i++; }else if(tmp[i][0]>tmp[j][0]){ arr[k][0] = tmp[j][0]; arr[k][1] = tmp[j][1]; for(int l=i;l<=mid;l++){ count+=tmp[j][1]-tmp[l][1]; } j++; } } return count; } }Java代码,用的归并排序方法,用二维数组分别记录值和索引,注意count要用long类型。
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int sum = 0; scanner.nextLine(); String str = scanner.nextLine(); String[] arrStr = str.split("\\s"); int[] arrInt = new int[arrStr.length]; for (int i = 0; i < arrStr.length; i++) { arrInt[i] = Integer.parseInt(arrStr[i]); } for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (arrInt[i] > arrInt[j]) { sum += (j - i); } } } System.out.println(sum); } }