The naive approach is obviously too slow for n up to 2*10^5.
Model the problem as selecting exactly k cheeses for Mouse 1 to maximize the sum of rewards, where each cheese has a different reward for each mouse. Transform the rewards into differences (reward1 - reward2) and choose the k cheeses with the largest positive differences, then compute the total reward. This reduces to sorting the differences and taking the top k, yielding an O(n log n) solution.
Pro tip: Always clarify edge cases like k=0 or k=n, and mention that if the differences are not distinct, any selection of top k works. Also, discuss potential follow-ups like handling large n or streaming data.
Restate the problem: assign exactly k cheeses to Mouse 1 and the remaining n-k to Mouse 2 to maximize total reward. Let reward1[i] and reward2[i] be the rewards for cheese i.
Compute the difference d[i] = reward1[i] - reward2[i] for each cheese. The total reward if Mouse 1 gets set S is sum(reward2) + sum_{i in S} d[i]. Thus, maximizing total reward is equivalent to maximizing the sum of d[i] over the k chosen cheeses.
Sort the differences in descending order and pick the first k cheeses. This greedy choice is optimal because the objective is linear and we want the largest positive contributions.
Sum the rewards for the chosen cheeses for Mouse 1 and the rewards for the remaining cheeses for Mouse 2. Alternatively, compute sum(reward2) + sum of top k differences.
The algorithm runs in O(n log n) due to sorting. Handle edge cases: k=0 (Mouse 1 gets nothing), k=n (Mouse 1 gets all), and negative differences (still must pick exactly k, so pick the least negative if necessary).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.