2551. Put Marbles in Bags
其实题目的意思就是把weights切成k的subarray
并且求出这些subarray头尾总和的最大值和最小值相减
从题目可以知道所有subarray总和一定会包含weights[0]和weights[n-1]
所以差异就是在其他元素
要把矩阵分成k等分就表示要切k-1刀
假设切在weights[i]那weights[i+1]就是下一个subarray的头
所以这题可以想成
求出所有weights[i]+weights[i+1](i = 0 ~ n-1)
然后前k-1大的组合 - 前k-1小的组合就是答案
golang code :
func putMarbles(weights []int, k int) int64 {
n := len(weights)
arr := make([]int, n-1)
for i := 0; i < n-1; i++ {
arr[i] = weights[i] + weights[i+1]
}
slices.Sort(arr)
ans := 0
for i := 0; i < k-1; i++ {
ans += (arr[n-2-i] - arr[i])
}
return int64(ans)
}

你好优秀