2551.将珠子放入背包中

链接：2551.将珠子放入背包中
难度：Hard
标签：贪心、数组、排序、堆（优先队列）
简介：一个珠子分配方案的 分数 是所有 k 个背包的价格之和。请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。

题解 1 - python

• 编辑时间：2023-01-29
• 执行用时：224ms
• 内存消耗：25.4MB
• 编程语言：python
• 解法介绍：同上。

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

题解 2 - rust

• 编辑时间：2023-01-29
• 执行用时：36ms
• 内存消耗：3.5MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn put_marbles(weights: Vec<i32>, k: i32) -> i64 {
        let mut list = Vec::new();
        for i in 1..weights.len() {
            list.push(weights[i - 1] + weights[i]);
        }
        list.sort();
        let fold = |sum, cur: &i32| sum + (*cur) as i64;
        list[list.len() - k as usize + 1..].iter().fold(0, fold)
            - list[..k as usize - 1].iter().fold(0, fold)
    }
}

题解 3 - rust

• 编辑时间：2023-01-29
• 执行用时：40ms
• 内存消耗：3.5MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn put_marbles(weights: Vec<i32>, k: i32) -> i64 {
        let mut list = Vec::new();
        for i in 1..weights.len() {
            list.push(weights[i - 1] + weights[i]);
        }
        list.sort();
        let mut ans = 0;
        for i in 0..k - 1 {
            let i = i as usize;
            ans += (list[list.len() - i - 1] - list[i]) as i64;
        }
        ans
    }
}

题解 4 - cpp

• 编辑时间：2023-01-29
• 执行用时：152ms
• 内存消耗：67.6MB
• 编程语言：cpp
• 解法介绍：贪心，只统计首位，当一个珠子当前组是末尾时，下一个珠子是下一组的首个。

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