小和问题

描述展开目录

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子展开目录

[1,3,4,2,5]
1 左边比 1 小的数：没有
3 左边比 3 小的数：1
4 左边比 4 小的数：1,3
2 左边比 2 小的数：1
5 左边比 5 小的数：1,3,4,2
所以小和为 1+1+3+1+1+3+4+2=16

解题思路展开目录

如果直接用两层 for 循环扫，时间复杂度是 $O (n^2)$，但是可以通过归并排序的方法将时间复杂度降到 O (nlogn)
具体做法：归并排序分两步，一是分，二是治。分好说，不停的将数组划分为两部分，比如样例，最终划分为如下图所示的样子
分完以后开始治，归并排序的治就是 merge 的过程，首先对 1 和 3 进行 merge，在此过程中产生一个小和 1；然后将 1、3 和 4 进行 merge，在此过程中产生小和 1、3；然后 2 和 5 进行 merge，产生小和 2；最后将 1、3、4 和 2、5 进行一次 merge，1 比 2 小，所以一共产生 n 个 1 的小和，这个 n 就是当前右边的数的个数，因为右边有两个数 2 和 5，所以产生 2 个 1 的小和，然后将 1 填入辅助数组，继续比较 3 和 2，2 比 3 小，但是 2 是右边的数，所以不算小和，然后比较 3 和 5，3 比 5 小，所以产生 n 个 3 的小和，因为右侧只有一个数，所以就只产生 1 个 3 的小和，同样的，产生 1 个 4 的小和
这道题换个角度来想，题目要求的是每个数左边有哪些数比自己小，其实不就是右边有多少个数比自己大，那么产生的小和就是当前值乘以多少个吗？还是以上面的样例举例，1 右边有 4 个比 1 大的数，所以产生小和 1*4；3 右边有 2 个比 3 大的数，所以产生小和 3*2；4 右边有一个比 4 大的数，所以产生小和 4*1；2 右边没有比 2 大的数，所以产生小和为 2*0；5 右边也没有比 5 大的数，所以产生小和 5*0

代码展开目录

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = cin.nextInt();
        System.out.println(smallSum(arr));
    }

    static int smallSum(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        return mergeSort(arr, 0, arr.length - 1);
    }

    static int mergeSort(int[] arr, int l, int r) {
        if (l == r)
            return 0;
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) + // 左侧产生的小和
                mergeSort(arr, mid + 1, r) + // 右侧产生的小和
                merge(arr, l, mid, r); // merge过程中产生的小和
    }

    static int merge(int[] arr,int l,int m,int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
        while(p1 <= m && p2 <= r) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m) 
            help[i++] = arr[p1++];
        while(p2 <= r)
            help[i++] = arr[p2++];
        for(i = 0;i < help.length;i++)
            arr[i + l] = help[i];
        return res;
    }
}