Jerry is very good at math
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy with detail and easy understanding math prove.\n\n### Approach\n Describe your a
### Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy with detail and easy understanding math prove.\n\n### Approach\n<!-- Describe your approach to solving the problem. -->\nAs $x_i \u2208 [0,1], a_i \u2208 reward1, b_i \u2208 reward2$\n$x_i=1$ means `mouse1` picks the i-th cheese of `reward1`\n$x_i=0$ means `mouse2` picks the i-th cheese of `reward2`\n$\\sum_{i = 1}^{n}x_i=x_1+x_2+...+x_n = k$\n\nWe can prove that the total points: `p`\n$p=x_1a_1+x_2a_2+...+x_na_n+\n    (1-x_1)b_1+(1-x_2)b_2+...+(1-x_n)b_n$\n$=(b_1+b_2 +...+ b_n)+(a_1-b_1)x_1+(a_2-b_2)x_2 +...+ (a_n-b_n)x_n$\n$=\\sum_{i = 1}^{n}b_i+\\sum_{i = 1}^{n}(a_i-b_i)x_i$\n\nSince $\\sum_{i = 1}^{n}b_i$ and $(a_i-b_i)$ are both constant, and $x_i \u2208 [0,1]$\nTo get maximum of `p`, we should pick top `k` value of $(a_i-b_i)$ with greedy, which means set $x_i=1$ for these $(a_i-b_i)$ and `mouse1` **only picks** these indice of cheese from `reward1`, `mouse2` pick the left indice of cheese from `reward2`.\n\n### Complexity\n- Time complexity: $$O(N*logN)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n### Code\n```\nclass Solution {\n  public int miceAndCheese(int[] reward1, int[] reward2, int k) {\n    final int n = reward1.length;\n    int points = 0;\n    for (int i = 0; i < n; i++) {\n      reward1[i] -= reward2[i];\n      points += reward2[i];\n    }\n\n    // pick top k\n    Arrays.sort(reward1);\n    for (int i = 0; i < k; i++) {\n      points += reward1[n - 1 - i];\n    }\n\n    return points;\n  }\n}\n```\n
['Math', 'Greedy', 'Sorting', 'Java']