炸鸡块君在高中时,学校规定进出校门必须要刷校园卡,否则禁止进入。
某一天,炸鸡块君和同学们一共nn个人去学校附近玩耍,但回学校时他们发现只有mm个人带了校园卡,于是他们想到了这样一个策略:先让mm个人带校园卡进入学校,再派一个人带着所有mm张校园卡出来,重复上述过程,直到所有人进入学校。
假设从外面进入学校和从校内出来到校外都需要花费一个单位的时间,求所有人都进入学校最少需要花费几个单位的时间。
用python3写
炸鸡块君在高中时,学校规定进出校门必须要刷校园卡,否则禁止进入。
某一天,炸鸡块君和同学们一共nn个人去学校附近玩耍,但回学校时他们发现只有mm个人带了校园卡,于是他们想到了这样一个策略:先让mm个人带校园卡进入学校,再派一个人带着所有mm张校园卡出来,重复上述过程,直到所有人进入学校。
假设从外面进入学校和从校内出来到校外都需要花费一个单位的时间,求所有人都进入学校最少需要花费几个单位的时间。
用python3写
时间复杂度O(1)
def total(nn, mm):
# 这些情况没办法进入
if mm <= 0 or nn <= 0 or (mm < 2 and nn > 1):
return -1
# 假设需要分n次进入学校: 不难看出,前n - 1次时间 = 2 * (n - 1)
# 最后一次时间为 1,总时间为 2 * (n - 1) + 1
# 每次最多能进mm个人,然后还要出来一个人,换句话来说,前 n - 1 次最多可以进入mm - 1个人,最后一次最多可以进入mm个人
# 即n需要满足不等式 (n - 1) * (mm - 1) + mm >= nn,当然充要条件为mm >= 2,并且nn != mm
return 1 if nn == mm else 2 * math.ceil((nn - mm) / (mm - 1) + 1) - 1