class Solution {
public:
long long putMarbles(vector<int>& weights, int k) {
}
};
6339. 将珠子放入背包中
你有 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 <= 1051 <= weights[i] <= 109原站题解
golang 解法, 执行用时: 180 ms, 内存消耗: 8.7 MB, 提交时间: 2023-01-30 11:29:53
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
}
cpp 解法, 执行用时: 136 ms, 内存消耗: 56 MB, 提交时间: 2023-01-30 11:29:39
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;
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 52.7 MB, 提交时间: 2023-01-30 11:29:25
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;
}
}
python3 解法, 执行用时: 292 ms, 内存消耗: 24.1 MB, 提交时间: 2023-01-30 11:29:07
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])