Basic
Intuition\nThe problem revolves around selecting rewards for mice from two arrays in a way that maximizes the total reward. The priority is to choose the higher
## Intuition\nThe problem revolves around selecting rewards for mice from two arrays in a way that maximizes the total reward. The priority is to choose the higher reward when `k` switches are allowed. The idea is to use a max-heap (priority queue) to make decisions based on the difference between the rewards in `reward1` and `reward2`.\n\n## Approach\n1. **Calculate Initial Total Reward**:\n   - Start by assuming all rewards are taken from `reward2`.\n   - Calculate the initial sum of rewards from `reward2`.\n\n2. **Use a Max-Heap (Priority Queue)**:\n   - Create a max-heap that stores pairs of the form `(difference, index)` where `difference` is the difference between `reward1` and `reward2`.\n   - The heap helps us to prioritize the largest differences first.\n\n3. **Modify Rewards Based on Priority Queue**:\n   - While we still have switches left (`k` is not zero), pop the maximum element from the heap.\n   - Adjust the total reward by switching the reward from `reward2` to `reward1` for the chosen index.\n   - Decrement `k` by one after each switch.\n\n4. **Return the Final Total Reward**:\n   - After using up all allowed switches, return the modified total reward.\n\nThis approach ensures that we are always making the optimal choice (i.e., the switch that gives the maximum additional reward).\n\n## Complexity\n- **Time Complexity**: \n  - Building the initial heap takes \\(O(n log n)\\) where \\(n\\) is the size of the rewards arrays.\n  - Adjusting the reward by popping from the heap \\(k\\) times takes \\(O(k log n)\\).\n\n  \n- **Space Complexity**:\n  - The space complexity is \\(O(n)\\) due to the storage of the heap.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n        \n        priority_queue<pair<int,int>> pq;\n        int ans = 0;\n\n        for(int i = 0;i<reward1.size();i++){\n            pq.push({reward1[i] - reward2[i], i} );\n            ans += reward2[i];\n        }\n\n        \n\n        while(k!=0){\n\n            ans = ans - reward2[pq.top().second] + reward1[pq.top().second];\n            pq.pop();\n            k--;\n\n        }\n\n        return ans;\n    }\n};\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']