"""
猴子偷桃问题：一共右n堆数目不一的桃子，猴子一个小时的偷桃数量大于当前桃子数目，他偷完桃子后需要等待；当小于当前挑子数量，那就需要一直再偷。
如果一共只有m个小时，最慢需要偷桃速度
"""
"""
案例：
list_num = [3,6,7,11], h=8
最新速度 4
list_num = [30.11.23.4,20], h=5
最新速度 30
解题思路：
假设最慢偷桃速度为1，最大为数组的最大值，在最小和最大值区间，选择中间数据，判断是否能够完成偷桃
"""
def min_steal_peach(list_num, h):
min_speed = 1
max_speed = max(list_num)
while min_speed < max_speed:
mid_speed = min_speed + int((max_speed-min_speed)/2)
if is_valid_speed(list_num, mid_speed, h):
max_speed = mid_speed
else:
min_speed = mid_speed + 1
return min_speed
def is_valid_speed(list_num, mid_speed, h):
res = 0
for i in list_num:
tmp = 1 if i % mid_speed != 0 else 0
res += int(i / mid_speed) + tmp
return True if res <= h else False
"""
案例——运货问题:有n堆货物需要从A城市运输到B城市，每堆货物不能分割,求在指定时间内，运完全部货物，求货船的最小载重
weights = [1,2,3,4,5,6,7,8,9,10]
D=5
output=15
解题思路：
假设船的最小载重为数组的最大值，最大载重为数组之和，在最小最大选择中间数据，判断该中间数据能否在规定时间运完货物
"""
def min_carrying_capacity(weights, D):
min_carrying = max(weights)
max_carrying = sum(weights)
while min_carrying < max_carrying:
mid_carrying = min_carrying + int((max_carrying - min_carrying) / 2)
if is_valid_carrying(weights, mid_carrying, D):
max_carrying = mid_carrying
else:
min_carrying = mid_carrying + 1
return min_carrying
def is_valid_carrying(weights, mid_carrying, D):
res = 0
tmp = mid_carrying
for i in weights:
if i <= tmp:
tmp -= i
else:
res += 1
tmp = mid_carrying - i
return True if res + 1 <= D else False #最后一次没有装满的情况
if __name__ == "__main__":
list_num = [3, 6, 7, 11]
h = 8
res = min_steal_peach(list_num, h)
print(res)
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
D = 5
output = min_carrying_capacity(weights, D)
print(output)