1518. 换酒问题

exiaohu 于 2021-12-17 发布

题目链接:1518. 换酒问题

解法一:模拟

模拟这个过程。

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        n_empty = numBottles
        while n_empty >= numExchange:
            newBottles = n_empty // numExchange

            n_empty %= numExchange
            n_empty += newBottles
            numBottles += newBottles

        return numBottles

解法二:数学

没想到竟然可以这么解,@淡烟流水画屏幽 的题解,解法很精妙。

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return (numBottles * numExchange - 1) // (numExchange - 1)

大意是,假设空瓶子价值为 $1$,因为 $N_{exchange}$ 个空瓶子可以换一瓶酒,那么装酒的瓶子的价值就是$N_{bottles} * N_{exchange}$。

最后至少手里会留一个空瓶子,因此换到酒的总价值就是$N_{bottles} * N_{exchange}-1$。

装酒的瓶子的价值等于酒的价值加上空瓶子的价值,因此酒的价值就是$N_{exchange}-1$。

最后喝到酒的数量就是

\[N_{alcohol} = \lfloor \frac{N_{bottles} * N_{exchange}-1}{N_{exchange}-1} \rfloor.\]