将珠子放入背包中

难度: Hard

你有 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 <= 10⁵
1 <= weights[i] <= 10⁹

Submission

运行时间: 160 ms

内存: 28.6 MB

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

Explain

题解的主要思路是首先计算所有相邻珠子的和，存储在一个数组中。然后将这个数组排序，以便于选出珠子组合的最大和最小值。具体步骤如下：1. 首先对于每一对相邻的珠子，计算它们的重量和，形成一个新的数组。2. 将这个新数组进行排序。3. 从排序后的数组中，为了获得最大分数，选择末尾的k-1个元素（因为这些是最大的k-1个组合），并计算它们的和。4. 同时，为了保证没有空背包，计算前k-1个元素（最小的k-1个组合）的和。5. 最终得分是最大组合和减去最小组合和。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        # 初始化存储每对相邻珠子之和的数组
        array = []
        n = len(weights)
        # 计算每对相邻珠子的和并存入array
        for i in range(1, n):
            array.append(weights[i] + weights[i - 1])
        # 对珠子组合的和进行排序
        array.sort()
        # 选取最大的k-1个组合的和, 由于排除了一个背包，实际上是从第k-1个元素开始计算
        return sum(array[len(array) - k + 1 : ]) - sum(array[ : k - 1])

Explore

排序这个数组是为了方便从中快速选取最大和最小的k-1个组合。如果不进行排序，直接在未排序的数组上寻找最大和最小的k-1个组合，将需要更复杂的算法（如使用优先队列或其他选择算法），这可能会增加时间复杂度。排序后，数组的最大和最小值可以直接通过索引访问，使得操作更为简单和高效。

选择最大的k-1个元素和最小的k-1个元素是为了最大化背包的价格差异，从而最大化整体分数。最大的k-1个组合提供了可能的最高价格，而最小的k-1个组合提供了可能的最低价格。通过计算这两者的差值，可以确保所有背包中的珠子组合都被考虑到，同时最大化了分数。这种方法确保了在满足所有背包都不为空的前提下，分数被最大化。

题解中的算法确实没有明确说明如何处理珠子数量不是k的整数倍的情形。算法假设了每个背包可以放置不同数量的珠子，只要这些珠子是连续的。然而，确实需要更详细的逻辑来确保在珠子数量不均等时，每个背包至少包含一个珠子，特别是处理边界情况，例如当珠子数量少于背包数量时。这可能需要调整算法以确保所有珠子都被合理地分配，避免有空背包的情况发生。