LCP 06. 拿硬币【向上取整】

Tag

【贪心】【数组】【2023-09-20】

---

题目来源

LCP 06. 拿硬币

---

题目解读

数组 coins 中存放的是一堆堆的力扣币，对于每一堆力扣币，你可以选择拿走一枚或者两枚，请返回拿走所有乐扣币的最少次数。

---

解题思路

方法一：贪心

我们利用贪心的思想来解决。

题目意思明确，对于每一堆的力扣币我们可以拿一枚也可以拿两枚，对于每一堆我们能拿两枚就拿两枚，不能拿两枚我们就拿一枚，这样拿完这一堆的力扣币次数最少，我们对每一堆拿取的次数最少（局部最优）促成了拿完所有力扣币的最少次数（全局最优）。

具体地，我们对 2 取上整，即可实现贪心策略。

a 对 b 取下整可以这样实现：$\lfloor \frac{a}{b}\rfloor =a/b$；a 对 b 取上整可以这样实现：$\lceil \frac{a}{b}\rceil =(a+b-1)/b=(b-1)/a+1$。

实现代码

1

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 coins 的长度。

空间复杂度：$O(1)$。

知识回顾

向上、向下取整

除了以上介绍的两种向上、向下取整方式之外，还有一些其他方法可以进行向上、向下取整。

需要强调的是向上、向下取整是对于浮点类型的取整，或者运算过程中出现的浮点类型取整。

对 x 向上取整是返回大于等于 x 的最小整数，用 $\lceil x\rceil$ 表示，比如 $\lceil 2.3\rceil =3$。计算方法有 ceil(x)，需要注意的是 ceil(x) 返回的是 double 类型、float 类型或者 long double 类型，具体的返回值类型适 x 的类型而定，使用完毕后还需要强转为整型数据。

对 x 向下取整是返回小于等于 x 的最大整数，用 $\lfloor x\rfloor$ 表示，比如 $\lfloor 2.3\rfloor =2$。计算方法有 floor(x)， floor(x) 返回的也是 double 类型、float 类型或者 long double 类型，具体的返回值类型适 x 的类型而定，使用完毕后还需要强转为整型数据。

对 x 向下取整操作还可以直接使用 int 类型进行强转，比如 $\lfloor 3.7\rfloor =(int)3.7=3$。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。