C++ | Sorting and Storing Differences | Easy to Understand
Intuition\n Describe your first thoughts on how to solve this problem. \nI don\'t know why I thought that DP would be used! \n\nThe intuition is to consider the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI don\'t know why I thought that DP would be used! \n\nThe intuition is to consider the difference in rewards between each cheese type for the two mice. We can create a vector of pairs where the first element of the pair is the difference in rewards and the second element is the index of the cheese type.\n\nThen, we can sort this vector in descending order based on the difference in rewards. We can then iterate through this sorted vector and choose the k highest differences, assigning those cheese types to the first mouse and the remaining cheese types to the second mouse.\n\nFinally, we can calculate the total score by adding up the rewards for each cheese type assigned to the first and second mouse respectively.\n\n\n# Complexity\n- Time complexity: The time complexity of this approach is O(n log n), where n is the number of cheese types, due to the sorting step. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(n) because we need to store the vector of pairs.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n        vector<pair<int,int>>diff;\n        int n=reward1.size();\n        for(int i=0;i<n;++i){\n            diff.push_back({reward1[i]-reward2[i],i});\n        }\n\n        sort(diff.begin(),diff.end(),greater<pair<int,int>>());\n\n        int score=0;\n        for(int i=0;i<n;++i){\n            if(k>0){\n                score+=reward1[diff[i].second];\n                k--;\n            }\n            else{\n                score+=reward2[diff[i].second];\n            }\n        }\n        return score;\n    }\n};\n```
['C++']