题目链接: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.\]