题目描述

java要用快读模板，题目本质就是求逆序对

样例

import java.util.*;
/*
  本题的实质就是在求逆序对。
  根据题意：该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排，找到所需的最小交换操作数。
  其实交换相邻的元素，会使逆序对的个数+1或-1，这里我们肯定是-1，操作的最少次数其实就是逆序对的个数。

*/


public class Main{
    static int N = 500010;
    static int[] a = new int[N];

    static long mergeSort(int left ,int right){
        if(left >= right) return 0;
        int mid = left + right >> 1;
        int i = left;
        int j = mid + 1;
        int k = 0;
        int[] temp = new int[N];
        long res = mergeSort(left,mid) + mergeSort(mid + 1, right);

        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];//不是逆序对就继续存放
            } else {
                temp[k++] = a[j++];//存放步骤不变
                //i右边都是>=本身,所以从大小上都符合逆序对的定义
                res += mid - i + 1;//统计逆序对的数量 
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }
        for (i = left, j = 0; i <= right; i++, j++) {
            a[i] = temp[j];
        }
        return res;

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n;
        while ((n = scanner.nextInt()) != 0) {
            a = new int[n + 1];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            System.out.println(mergeSort(0, n-1));
        }
    }
}