Question

1561. 你可以获得的最大硬币数目

English Version

题目描述

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

• 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
• Alice 将会取走硬币数量最多的那一堆。
• 你将会取走硬币数量第二多的那一堆。
• Bob 将会取走最后一堆。
• 重复这个过程，直到没有更多硬币。

给你一个整数数组 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^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

解法

方法一：贪心

Bob 取走最小的 1/3，剩余的硬币堆由 Alice 和我按硬币数从高到低依次取走每一堆。

class Solution:
  def maxCoins(self, piles: List[int]) -> int:
    piles.sort()
    return sum(piles[-2 : len(piles) // 3 - 1 : -2])

class Solution {

  public int maxCoins(int[] piles) {
    Arrays.sort(piles);
    int ans = 0;
    for (int i = piles.length - 2; i >= piles.length / 3; i -= 2) {
      ans += piles[i];
    }
    return ans;
  }
}

class Solution {
public:
  int maxCoins(vector<int>& piles) {
    sort(piles.begin(), piles.end());
    int ans = 0;
    for (int i = piles.size() - 2; i >= (int) piles.size() / 3; i -= 2) ans += piles[i];
    return ans;
  }
};

func maxCoins(piles []int) int {
  sort.Ints(piles)
  ans, n := 0, len(piles)
  for i := n - 2; i >= n/3; i -= 2 {
    ans += piles[i]
  }
  return ans
}

function maxCoins(piles: number[]): number {
  piles.sort((a, b) => a - b);
  const n = piles.length;
  let ans = 0;
  for (let i = 1; i <= Math.floor(n / 3); i++) {
    ans += piles[n - 2 * i];
  }
  return ans;
}

impl Solution {
  pub fn max_coins(mut piles: Vec<i32>) -> i32 {
    piles.sort();
    let n = piles.len();
    let mut ans = 0;
    for i in 1..=n / 3 {
      ans += piles[n - 2 * i];
    }
    ans
  }
}

int cmp(const void* a, const void* b) {
  return *(int*) a - *(int*) b;
}

int maxCoins(int* piles, int pilesSize) {
  qsort(piles, pilesSize, sizeof(int), cmp);
  int ans = 0;
  for (int i = 1; i <= pilesSize / 3; i++) {
    ans += piles[pilesSize - 2 * i];
  };
  return ans;
}