class Solution {
public:
int maxCoins(vector<int>& piles) {
}
};
1561. 你可以获得的最大硬币数目
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
示例 1：
输入：piles = [2,4,1,2,7,8] 输出：9 解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。 选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。 你可以获得的最大硬币数目：7 + 2 = 9. 考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：
输入：piles = [2,4,5] 输出：4
示例 3：
输入：piles = [9,8,7,6,5,1,2,3,4] 输出：18
提示：
3 <= piles.length <= 10^5piles.length % 3 == 01 <= piles[i] <= 10^4原站题解
cpp 解法, 执行用时: 40 ms, 内存消耗: 55.9 MB, 提交时间: 2025-01-22 00:09:52
class Solution {
public:
int maxCoins(vector<int>& piles) {
ranges::sort(piles);
int n = piles.size();
int ans = 0;
for (int i = n / 3; i < n; i += 2) {
ans += piles[i];
}
return ans;
}
};
javascript 解法, 执行用时: 119 ms, 内存消耗: 59.3 MB, 提交时间: 2025-01-22 00:09:37
/**
* @param {number[]} piles
* @return {number}
*/
var maxCoins = function(piles) {
piles.sort((a, b) => a - b);
const n = piles.length;
let ans = 0;
for (let i = n / 3; i < n; i += 2) {
ans += piles[i];
}
return ans;
};
rust 解法, 执行用时: 7 ms, 内存消耗: 3.4 MB, 提交时间: 2025-01-22 00:09:23
impl Solution {
pub fn max_coins(mut piles: Vec<i32>) -> i32 {
piles.sort_unstable();
piles[piles.len() / 3..].iter().step_by(2).sum()
}
}
golang 解法, 执行用时: 27 ms, 内存消耗: 9.7 MB, 提交时间: 2025-01-22 00:09:10
func maxCoins(piles []int) (ans int) {
slices.Sort(piles)
n := len(piles)
for i := n / 3; i < n; i += 2 {
ans += piles[i]
}
return
}
java 解法, 执行用时: 30 ms, 内存消耗: 55.1 MB, 提交时间: 2025-01-22 00:08:58
class Solution {
public int maxCoins(int[] piles) {
Arrays.sort(piles);
int n = piles.length;
int ans = 0;
for (int i = n / 3; i < n; i += 2) {
ans += piles[i];
}
return ans;
}
}
python3 解法, 执行用时: 116 ms, 内存消耗: 23.9 MB, 提交时间: 2022-11-11 11:06:41
class Solution:
def maxCoins(self, piles: List[int]) -> int:
'''
策略就是每次取最大的两个+最小的那堆之一，bob取最小的那堆，自己取中间那堆
'''
n = len(piles)
piles.sort()
return sum(piles[n // 3 :: 2])