题解 | 计算数组的小和

package main

import (
    "fmt"
)

func main() {
    num := 0
    for {
        n, _ := fmt.Scan(&num)
        if n == 0 {
            break
        } else {
            arr := make([]int, num)
            for i:=0; i<num; i++ {
                fmt.Scan(&arr[i])
            }
            fmt.Println(process(arr,0, len(arr)-1))
        }
    }
}
// 计算小数和，转换问题为，
// 在位置i处，arr[i] 右边大于等于arr[i]的数有多少个, 假设有N个
// sum += arr[i] * N
// 联想到归并排序，部分有序，左边找右边有多少个数大于这个数，累加求和。
func process(arr []int,l, r int) int{
    if l >= r {
        return 0
    }
    mid := (r-l)/2+l
    sum1 := process(arr, l, mid)
    sum2 := process(arr, mid+1, r)
    return sum1+sum2+merge(arr, l, mid, r) 
}
func merge(arr []int, l, mid, r int) int{
    tmp := make([]int, r-l+1)
    li, rj := l, mid+1
    sum := 0
    i := 0
    for li <= mid && rj<=r {
        if arr[li] <= arr[rj] {
            tmp[i] = arr[li]
            sum += arr[li] * (r-rj+1) // 在位置i处，arr[i] 右边大于等于arr[i]的数有r-rj+1个
            li++
        } else {
            tmp[i] = arr[rj]
            rj++
        }
        i++
    }
    for li <= mid {
        tmp[i] = arr[li]
        li++
        i++
    }
    for rj <= r {
        tmp[i] = arr[rj]
        rj++
        i++
    }

    for i:=0; i<len(tmp); i++ {
        arr[l+i] = tmp[i]
    }
    return sum
}