AcWing 788. 逆序对的数量-golang
原题链接
简单
作者:
渲染
,
2024-03-30 15:15:54
,
所有人可见
,
阅读 1
package main
import "fmt"
const N int = 100000
var nums = [N]int{}
var temp = [N]int{}
func merge_sort(left , right int) int{
if left >= right {
return 0
}
mid := (left + right) >> 1
ans := merge_sort(left,mid)+merge_sort(mid+1,right)
i , j := left,mid+1
var k int
for i <= mid && j <= right{
if nums[i] <= nums[j]{
temp[k] = nums[i]
i++
}else{
temp[k] = nums[j]
ans += mid-i+1
j++
}
k++
}
for i<=mid{
temp[k] = nums[i]
i++
k++
}
for j <= right{
temp[k] = nums[j]
k++
j++
}
i = left
j = 0
for i<=right{
nums[i] = temp[j]
j++
i++
}
return ans
}
func main(){
var n int
fmt.Scan(&n)
for i:=0;i<n;i++{
fmt.Scan(&nums[i])
}
ans := merge_sort(0,n-1)
fmt.Println(ans)
}