Question

2551. 将珠子放入背包中

English Version

题目描述

你有 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

解法

方法一：问题转化 + 排序

我们可以将问题转化为：将数组 weights 分成 $k$ 个连续的子数组，也就是说，我们要找到 $k-1$ 个分割点，每个分割点的价格是分割点左右两个元素的和，求最大的 $k-1$ 个分割点的价格之和与最小的 $k-1$ 个分割点的价格之和的差值，即为答案。

因此，我们可以处理数组 weights，将其转化为一个长度为 $n-1$ 的数组 arr，其中 arr[i] = weights[i] + weights[i+1]，然后对数组 arr 进行排序，最后求出最大的 $k-1$ 个分割点的价格之和与最小的 $k-1$ 个分割点的价格之和的差值即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 weights 的长度。

class Solution:
  def putMarbles(self, weights: List[int], k: int) -> int:
    arr = sorted(a + b for a, b in pairwise(weights))
    return sum(arr[len(arr) - k + 1 :]) - sum(arr[: k - 1])

class Solution {
  public long putMarbles(int[] weights, int k) {
    int n = weights.length;
    int[] arr = new int[n - 1];
    for (int i = 0; i < n - 1; ++i) {
      arr[i] = weights[i] + weights[i + 1];
    }
    Arrays.sort(arr);
    long ans = 0;
    for (int i = 0; i < k - 1; ++i) {
      ans -= arr[i];
      ans += arr[n - 2 - i];
    }
    return ans;
  }
}

class Solution {
public:
  long long putMarbles(vector<int>& weights, int k) {
    int n = weights.size();
    vector<int> arr(n - 1);
    for (int i = 0; i < n - 1; ++i) {
      arr[i] = weights[i] + weights[i + 1];
    }
    sort(arr.begin(), arr.end());
    long long ans = 0;
    for (int i = 0; i < k - 1; ++i) {
      ans -= arr[i];
      ans += arr[n - 2 - i];
    }
    return ans;
  }
};

func putMarbles(weights []int, k int) (ans int64) {
  n := len(weights)
  arr := make([]int, n-1)
  for i, w := range weights[:n-1] {
    arr[i] = w + weights[i+1]
  }
  sort.Ints(arr)
  for i := 0; i < k-1; i++ {
    ans += int64(arr[n-2-i] - arr[i])
  }
  return
}

function putMarbles(weights: number[], k: number): number {
  const n = weights.length;
  const arr: number[] = [];
  for (let i = 0; i < n - 1; ++i) {
    arr.push(weights[i] + weights[i + 1]);
  }
  arr.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0; i < k - 1; ++i) {
    ans += arr[n - i - 2] - arr[i];
  }
  return ans;
}