2551-将珠子放入背包中

你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i
个珠子的重量。同时给你整数 k 。

请你按照如下规则将所有的珠子放进 k 个背包。

• 没有背包是空的。
• 如果第 i 个珠子和第 j 个珠子在同一个背包里，那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中。
• 如果一个背包有下标从 i 到 j 的所有珠子，那么这个背包的价格是 weights[i] + weights[j] 。

一个珠子分配方案的 分数 是所有 k 个背包的价格之和。

请你返回所有分配方案中， 最大分数 与 最小分数 的 差值 为多少。

示例 1：

**输入：** weights = [1,3,5,1], k = 2
**输出：** 4
**解释：**
分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。
分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。
所以差值为 10 - 6 = 4 。

示例 2：

**输入：** weights = [1, 3], k = 2
**输出：** 0
**解释：** 唯一的分配方案为 [1],[3] 。
最大最小得分相等，所以返回 0 。

提示：

• 1 <= k <= weights.length <= 105
• 1 <= weights[i] <= 109

提示 1

问题相当于把 weights 划分成 k 个连续子数组，分数等于每个子数组的两端的值之和。

提示 2

weights}[0] 和 weights}[n-1] 一定在分数中，最大分数和最小分数相减，抵消了。

上一个子数组的末尾和下一个子数组的开头一定同时在分数中。

提示 3

把所有 n-1 个 weights}[i]+\textit{weights}[i+1] 算出来，排序，那么最大的 k-1 个数和最小的 k-1 个数相减，即为答案。

附：视频讲解

[sol1-Python3]

class Solution:
    def putMarbles(self, wt: List[int], k: int) -> int:
        for i in range(len(wt) - 1):
            wt[i] += wt[i + 1]
        wt.pop()
        wt.sort()
        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])

[sol1-Java]

class Solution {
    public long putMarbles(int[] wt, int k) {
        int n = wt.length;
        for (int i = 0; i < n - 1; ++i)
            wt[i] += wt[i + 1];
        Arrays.sort(wt, 0, n - 1); // 相当于去掉最后一个数
        long ans = 0;
        for (int i = 0; i < k - 1; ++i)
            ans += wt[n - 2 - i] - wt[i];
        return ans;
    }
}

[sol1-C++]

class Solution {
public:
    long long putMarbles(vector<int> &wt, int k) {
        int n = wt.size();
        for (int i = 0; i < n - 1; ++i)
            wt[i] += wt[i + 1];
        sort(wt.begin(), wt.end() - 1); // 相当于去掉最后一个数
        long ans = 0;
        for (int i = 0; i < k - 1; ++i)
            ans += wt[n - 2 - i] - wt[i];
        return ans;
    }
};

[sol1-Go]

func putMarbles(wt []int, k int) (ans int64) {
	for i, w := range wt[1:] {
		wt[i] += w
	}
	wt = wt[:len(wt)-1]
	sort.Ints(wt)
	for _, w := range wt[len(wt)-k+1:] {
		ans += int64(w)
	}
	for _, w := range wt[:k-1] {
		ans -= int64(w)
	}
	return
}

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)。忽略排序的栈空间，仅用到若干额外变量。