2611.老鼠和奶酪

链接：2611.老鼠和奶酪
难度：Medium
标签：贪心、数组、排序、堆（优先队列）
简介：给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组。

题解 1 - cpp

• 编辑时间：2023-04-02
• 执行用时：132ms
• 内存消耗：107.6MB
• 编程语言：cpp
• 解法介绍：贪心找价值比最高的。

class Solution {
   public:
    typedef pair<int, int> pii;
    int miceAndCheese(vector<int> &reward1, vector<int> &reward2, int k) {
        int n = reward1.size();
        vector<pii> list;
        for (int i = 0; i < n; i++) {
            list.push_back(make_pair(reward1[i], reward2[i]));
        }
        sort(list.begin(), list.end(), [](auto &a, auto &b) {
            int v1 = a.second - a.first, v2 = b.second - b.first;
            return v1 < v2;
        });
        int res = 0, i = 0;
        while (k--) res += list[i++].first;
        while (i < n) res += list[i++].second;
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-04-02
• 执行用时：184ms
• 内存消耗：32.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        n = len(reward1)
        l: List[(int, int)] = []
        for i in range(n):
            l.append((reward1[i], reward2[i]))
        l.sort(key=lambda v: v[1] - v[0])
        res = i = 0
        while k:
            res += l[i][0]
            i += 1
            k -= 1
        while i < n:
            res += l[i][1]
            i += 1
        return res

题解 3 - rust

• 编辑时间：2023-04-02
• 执行用时：28ms
• 内存消耗：4.3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn mice_and_cheese(reward1: Vec<i32>, reward2: Vec<i32>, mut k: i32) -> i32 {
        let n = reward1.len();
        let mut list: Vec<(i32, i32)> = vec![];
        for i in 0..n {
            list.push((reward1[i], reward2[i]));
        }
        list.sort_by_key(|v| (*v).1 - (*v).0);
        let mut res = 0;
        let mut i = 0;
        while k != 0 {
            res += list[i].0;
            i += 1;
            k -= 1;
        }
        while i < n {
            res += list[i].1;
            i += 1;
        }
        res
    }
}

题解 4 - cpp

• 编辑时间：2023-06-07
• 执行用时：312ms
• 内存消耗：103.5MB
• 编程语言：cpp
• 解法介绍：哈希存储。

#define SORT(list, fn) sort(list.begin(), list.end(), [&](auto &v1, auto &v2){ fn });
class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size(), res = 0;
        vector<int> idxs;
        for (int i = 0; i < n; i++) idxs.push_back(i);
        SORT(idxs, { return reward1[v1] - reward2[v1] < reward1[v2] - reward2[v2]; });
        for (int i = 0; i < n - k; i++) res += reward2[idxs[i]];
        for (int i = n - k; i < n; i++) res += reward1[idxs[i]];
        return res;
    }
};