题目链接
分析
对于每次取出的 $3$ 堆硬币，我们可以取走数量第二多的那堆。那么我们使用贪心的思想，第一次拿出的 $3$ 堆硬币，将整个堆中的最多的的一堆给 Alice，自己拿走第二多的堆，并将整个堆中最小的一堆拿出来给 Bob
以此类推，我们可以拿到从大到小排序后下标为 $1, 3, 5, \cdots, 2m-3, 2m-1\ (m=n/3)$ 的硬币堆
代码实现
class Solution {
public:
int maxCoins(vector<int>& piles) {
ranges::sort(piles, greater<>());
int ans = 0;
int n = piles.size() / 3;
for(int i = 1; i < n * 2; i += 2) {
ans += piles[i];
}
return ans;
}
};
复杂度分析
- 时间复杂度：$O(n\log n)$，排序的时间开销
- 空间复杂度：$O(1)$
