桌上有 n
堆力扣币,每堆的数量保存在数组 coins
中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。
示例 1:
示例 2:
限制:
1 <= n <= 4
1 <= coins[i] <= 10
解法 贪心
因为每次操作我们只能取一堆力扣币进行拿取操作,所以拿光不同堆力扣币的次数相互独立,所以求拿光全部力扣币的最少操作次数等价于求拿光每一堆力扣币的最少次数。
对于拿光有 m m m , m > 0 m > 0 m>0 枚的一堆力扣币,我们设拿了两枚力扣币的操作次数为 x x x ,拿一枚力扣币的操作次数为 y y y ,则有 2 × x + y = m 2 \times x + y = m 2×x+y=m 。
因此我们需要使 x + y x + y x+y 最小。因为 x + y = m − x x + y = m - x x+y=m−x ,所以我们要尽可能的进行拿两枚力扣币的操作,有: x = ⌊ m 2 ⌋ x = \lfloor \frac{m}{2} \rfloor x=⌊2m⌋ , y = m − 2 × ⌊ m 2 ⌋ y = m - 2 \times \lfloor \frac{m}{2} \rfloor y=m−2×⌊2m⌋ ,此时我们需要的最少操作次数为 x + y = ⌈ m 2 ⌉ x + y = \lceil \frac{m}{2} \rceil x+y=⌈2m⌉ 。因此拿完所有力扣币的最少次数为 ∑ i = 0 n − 1 ⌈ coins [ i ] 2 ⌉ \sum_{i = 0}^{n-1} \lceil \frac{\textit{coins}[i]}{2} \rceil i=0∑n−1⌈2coins[i]⌉
,其中 coins [ i ] \textit{coins}[i] coins[i] 表示第 i i i 堆力扣币的个数, n n n 为总的力扣币堆数。
class Solution {
public:
int minCount(vector<int>& coins) {
int sum = 0;
for (int& i : coins) sum += (i + 1) / 2;
return sum;
}
};