LCP 06-拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

限制：

• 1 <= n <= 4
• 1 <= coins[i] <= 10

方法一：贪心

思路与算法

对于拿光有 m，m > 0 枚的一堆力扣币，我们设拿了两枚力扣币的操作次数为 x，拿一枚力扣币的操作次数为 y，则有 2 \times x + y = m。因为每次操作我们只能取一堆力扣币进行拿取操作，所以拿光不同堆力扣币的次数相互独立，所以求拿光全部力扣币的最少操作次数等价于求拿光每一堆力扣币的最少次数。因此我们需要使 x + y 最小。因为 x + y = m - x，所以我们要尽可能的进行拿两枚力扣币的操作，有：x = \lfloor m}{2} \rfloor，y = m - 2 \times \lfloor m}{2} \rfloor，此时我们需要的最少操作次数为 x + y = \lceil m}{2} \rceil。因此拿完所有力扣币的最少次数为 \sum_{i = 0}^{n-1} \lceil \textit{coins}[i]}{2} \rceil，其中 coins}[i] 表示第 i 堆力扣币的个数，n 为总的力扣币堆数。

代码

[sol1-Python3]

class Solution:
    def minCount(self, coins: List[int]) -> int:
        return sum((i + 1) // 2 for i in coins)

[sol1-Java]

class Solution {
    public int minCount(int[] coins) {
        int sum = 0;
        for (int i : coins) {
            sum += (i + 1) / 2;
        }
        return sum;
    }
}

[sol1-C#]

public class Solution {
    public int MinCount(int[] coins) {
        int sum = 0;
        foreach (int i in coins) {
            sum += (i + 1) / 2;
        }
        return sum;
    }
}

[sol1-C++]

class Solution {
public:
    int minCount(vector<int>& coins) {
        int sum = 0;
        for (int& i : coins) {
            sum += (i + 1) / 2;
        }
        return sum;
    }
};

[sol1-Go]

func minCount(coins []int) int {
    sum := 0
    for _, i := range coins {
        sum += (i + 1) / 2
    }
    return sum
}

[sol1-JavaScript]

var minCount = function(coins) {
    let sum = 0;
    for (let i = 0; i < coins.length; i++) {
        sum += parseInt((coins[i] + 1) / 2);
    }
    return sum;
};

[sol1-C]

int minCount(int* coins, int coinsSize){
    int sum = 0;
    for (int i = 0; i < coinsSize; i++) {
        sum += (coins[i] + 1) / 2;
    }
    return sum;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 coins 的长度。
• 空间复杂度：O(1)，仅使用常量空间。