2611. Mice and Cheese

sort

```java
class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int result = 0;
        for (int num : reward2) {
            result += num;
        }
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) {
            diff[i] = reward1[i] - reward2[i];
        }
        Arrays.sort(diff);
        for (int i = n-1; i >= n-k; i--) {
            result += diff[i];
        }
        return result;
    }
}
/*
this question actually ask choose k larget in rewards1
the choose left (n-k) values in rewards2  (not both choose k....) the question is confusing!!!!

so ans we can do like this 
add all rewards2 values -> ans += rewards2

then cal rewards1[i] - rewards2[i], sort by desc
then only add these k larget diff to ans -> it's the ans!

rewards2 part + (rewards1[i] - rewards2[i]) -> k largest rewards1[i] 

T: O(nlogn)
S: O(n)
*/
```

using Heap to get K largest

```java
class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int result = 0;
        for (int num : reward2) {
            result += num;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            minHeap.offer(reward1[i] - reward2[i]);
            while (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        while (!minHeap.isEmpty()) {
            result += minHeap.poll();
        }
        return result;
    }
}
/* 

T: O(nlogk)
S: O(k)
*/
```

using quick selct

T: O(n)

S: O(n