2611_MiceandCheese - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        // HINT 2 
        // Imagine at first that the second mouse eats all the cheese, then we should choose k types of cheese with the maximum sum of - reward2[i] + reward1[i].
        priority_queue<vector<int>, vector<vector<int>> >pq;
        int n =reward1.size();
        int r = 0;
        vector<bool> visited(n, false);
        for(int i= 0 ;i < n; ++i) pq.push({reward1[i] - reward2[i] , i});
        while(k--){
            vector t = pq.top();
            pq.pop();
            visited[t.back()] = true;
            r+= reward1[t.back()];
        }
        for(int i=0;i<n;++i) r+= !visited[i]?reward2[i]:0;
        return r;
    }
};

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        // HINT 2 
        // Imagine at first that the second mouse eats all the cheese, then we should choose k types of cheese with the maximum sum of - reward2[i] + reward1[i].
        priority_queue<vector<int>, vector<vector<int>> >pq;
        int n =reward1.size();
        int r = 0;
        for(int i= 0 ;i < n; ++i) pq.push({reward1[i] - reward2[i] , i});
        for(int i=0;i<n;++i) {
            vector t = pq.top();
            pq.pop();
            if(k>0) r+= reward1[t.back()];
            else r+= reward2[t.back()];
            k--;
        }
        return r;
    }
};

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        int r = 0;
        for(int i=0;i<n;++i) {
            reward1[i] -= reward2[i];
            r+=reward2[i];
        }
        sort(reward1.begin(), reward1.end());
        for(int i=0;i<k;++i) r+=reward1[n-1-i];
        return r;
    }
};