LeetCode LCP 06. 拿硬币【贪心,数学】简单

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

桌上有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 = ⌊ m2⌋x = \lfloor \frac{m}{2} \rfloorx=⌊2m​⌋ ， y = m − 2 × ⌊ m2⌋y = m – 2 \times \lfloor \frac{m}{2} \rfloory=m−2×⌊2m​⌋ ，此时我们需要的最少操作次数为 x+y=⌈ m 2⌉x + y = \lceil \frac{m}{2} \rceil x+y=⌈2m​⌉ 。因此拿完所有力扣币的最少次数为 ∑ i=0n−1 ⌈ coins[i]2⌉\sum_{i = 0}^{n-1} \lceil \frac{\textit{coins}[i]}{2} \rceil i=0∑n−1​⌈2coins[i]​⌉
​，其中 $\text{coins}[i]$ 表示第 $i$ 堆力扣币的个数，$n$ 为总的力扣币堆数。

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