→ Rushia: 你好優秀 03/31 23:37
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)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743435111.A.924.html