主体思路
归并排序(分治思想)的巧妙应用
会有三种情况:
1. 都在左边 递归左边
2. 都在右边 递归右边
3. 一左一右,在合并的时候,第一次遇到nums[i] > nums[j],这时逆序对的个数不就是mid - i + 1
答案就是3情况的加总
注意细节
【结果的大小】
输出结果可能会爆int,最好用上int64
在go中,直接用int就好,至少在这题没有爆
基础代码
package main
import (
"bufio"
"os"
"fmt"
)
var (
n int
nums, tmp []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func mergeSort(l, r int) (res int64) {
if l >= r { return 0 }
mid := l + (r - l) >> 1
res = mergeSort(l, mid) + mergeSort(mid + 1, r)
k, i, j := 0, l, mid + 1
for i <= mid && j <= r {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
k += 1; i += 1
} else {
res += int64(mid - i + 1)
tmp[k] = nums[j]
k += 1; j += 1
}
}
for i <= mid {
tmp[k] = nums[i]
k += 1; i += 1
}
for j <= r {
tmp[k] = nums[j]
k += 1; j += 1
}
for a, b := l, 0; a <= r; a, b = a + 1, b + 1 { nums[a] = tmp[b] }
return
}
func main() {
fmt.Fscan(in, &n)
nums, tmp = make([]int, n), make([]int, n)
for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) }
fmt.Fprint(out, mergeSort(0, n - 1))
out.Flush()
}