💯✔ DAY 367 || [JAVA/C++/PYTHON] || EXPLAINED || INTUITION || APPROACH || ALGORITHM || O(N)
Please Upvote as it really motivates me\n\n Describe your approach to solving the problem. \n##### \u2022\tIntuition: \n##### \u2022\tThe problem involves findi
# Please Upvote as it really motivates me\n\n<!-- Describe your approach to solving the problem. -->\n##### \u2022\tIntuition: \n##### \u2022\tThe problem involves finding the optimal way for mice to reach cheese in a maze. \n##### \u2022\tThe goal is to minimize the total distance traveled by the mice. \n##### \u2022\tApproach: \n##### \u2022\tCalculate the difference between the positions of each mouse and cheese. \n##### \u2022\tSort the differences in descending order. Add up the first k elements of the sorted differences array to get the sum of the positions of the k mice that are closest to the cheese. \n##### \u2022\tAdd the sum of the positions of all the cheese in the maze to the sum of the positions of the k mice to get the total distance traveled. \n##### \u2022\tAlgorithm: \n##### \u2022\tInitialize a variable res to 0 to store the result.\n##### \u2022\tCalculate the length of the input arrays A and B . \n##### \u2022\tCreate a new array diff of length n to store the differences between the elements of A and B .\n##### \u2022\tIterate over the elements of A and B and calculate the difference between them, storing the result in diff . \n##### \u2022\tAdd up the elements of B and store the result in res . Sort the diff array in descending order. \n##### \u2022\tIterate over the first k elements of the sorted diff array and add them to res . Return res as the total distance traveled.\n\n\n\n# Code\n```python []\n    def miceAndCheese(self, a: List[int], b: List[int], k: int) -> int:\n        ans = 0\n        pq = []\n        for i in range(len(a)):\n            heapq.heappush(pq, -(a[i]-b[i])) # difference of r1-r2\n            ans += b[i]\n        for i in range(k):\n            ans -= heapq.heappop(pq)\n        return ans\n```\n```java []\npublic int miceAndCheese(int[] a, int[] b, int k) {\n        int len =a.length,ans=0;\n        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());\n        for(int i=0;i<len;i++) {\n            pq.offer(a[i]-b[i]);//diffrenece of r1-r2\n            ans+=b[i];\n        }\n        for(int i=0;i<k;i++) ans+=pq.poll();\n        return ans;\n    }\n```\n```c++ []\nint miceAndCheese(vector<int>& a, vector<int>& b, int k) {\n    int n = a.size(), ans = 0;\n    priority_queue<int> pq;\n    for (int i = 0; i < n; i++) {\n        pq.push(a[i] - b[i]); // difference of r1-r2\n        ans += b[i];\n    }\n    for (int i = 0; i < k; i++) {\n        ans -= pq.top();\n        pq.pop();\n    }\n    return ans;\n}\n```\n\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n\u2022 Thanks for visiting my solution.\uD83D\uDE0A Keep Learning\n\u2022 Please give my solution an upvote! \uD83D\uDC4D\n\u2022 It\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n
['Python', 'C++', 'Java', 'Python3']