Maximum Number of Coins You Can Get
Problem
There are 3n piles of coins. In each turn: Alice picks the largest pile, you pick the next-largest, Bob picks the smallest. Repeat n turns; return the maximum coins YOU can collect.
piles=[2,4,1,2,7,8]9def max_coins(piles):
a = sorted(piles)
n = len(a) // 3
return sum(a[-2 - 2*i] for i in range(n))function maxCoins(piles) {
const a = piles.slice().sort((x, y) => x - y);
const n = a.length / 3;
let ans = 0;
for (let i = 0; i < n; i++) ans += a[a.length - 2 - 2 * i];
return ans;
}class Solution {
public int maxCoins(int[] piles) {
Arrays.sort(piles);
int n = piles.length / 3, ans = 0;
for (int i = 0; i < n; i++) ans += piles[piles.length - 2 - 2 * i];
return ans;
}
}int maxCoins(vector& piles) {
sort(piles.begin(), piles.end());
int n = piles.size() / 3, ans = 0;
for (int i = 0; i < n; i++) ans += piles[piles.size() - 2 - 2 * i];
return ans;
} Explanation
Each round Alice grabs the largest pile, you grab the second largest, and Bob grabs the smallest. The smart move is to realize that Bob is going to get the small piles no matter what, so we should "sacrifice" the smallest piles to him and fight over the big ones.
After sorting ascending, the smallest n piles all go to Bob (the bottom third). From the remaining top 2n piles, they come in pairs — Alice takes the bigger, you take the smaller of each pair.
So your coins are every second pile counting down from near the top. The code uses a[-2 - 2*i]: index -2 (second biggest) is your first pick, -4 is your next, and so on.
Example: piles=[2,4,1,2,7,8] sorted is [1,2,2,4,7,8], with n=2. Bob takes 1 and 2. You take a[-2]=7 and a[-4]=2.
Adding your picks gives 7 + 2 = 9. Alice quietly takes 8 and 4, but those were always out of your reach.