51-Nod 1019 逆序数

第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

输出逆序数

4
2
4
3
1

4

分析：最开始写这道题的时候，一看觉得不是很简单吗，直接用双重循环进弄出来了，

没想到，提交上去，代码一跑，最后5个测试用例超时了，就明白了是自己的代码时间复杂度太高，

然后使劲想啊，结果黄天不负有心人啊，想到了用分治归并的思想，也就是归并排序的思想，结果AC了

代码如下，

import java.util.*;
import java.io.*;
// public class Main{
//     public static void main(String[] args){
//         Scanner s = new Scanner(System.in);
//         PrintWriter out = new PrintWriter(System.out);
//         int N = s.nextInt();
//         int[] arr = new int[N];
//         for(int i=0; i<N; ++i)
//           arr[i] = s.nextInt();
//         int count =0;
//         for(int i=0; i<N; ++i)
//           for(int j=i+1; j<N; ++j){
//               if(arr[i]>arr[j])
//                  count++;
//           }
//         out.println(count);
//         out.flush();
//     }
// }


public class Main{
        static int N; 
        static int[] arr = null;
        static int[] tem = null;
        static int count =0;
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        N = s.nextInt();
        arr = new int[N];
        tem = new int[N];
        for(int i=0; i<N; ++i)
          arr[i] = s.nextInt();
        int start = 0;
        int end = arr.length-1;
        merger(start,end);
        out.println(count);
        out.flush();
    }
    public static void merger(int start, int end){
        if(start<end){
            int mid = start+(end-start)/2;
            merger(start,mid);
            merger(mid+1,end);
            mergeAndCount(start,mid,end);
        }
    }
    public static void mergeAndCount(int s,int m, int e){
        int i = s;
        int j = m+1;
        int index =0;
        while(i<=m && j<=e){
            if(arr[i]>arr[j]){
               count+=e-j+1;
               tem[index++] = arr[i];
               i++;
            }else{
                tem[index++] = arr[j];
                j++;
            }
        }
        while(i<=m)
           tem[index++] = arr[i++];
        while(j<=e)
           tem[index++] = arr[j++];
        for(int k=0; k<e-s+1; ++k)
        arr[s+k] = tem[k];
    }
}