腾讯，秋招算法笔试，第三题：杂货店冰淇淋个数
小明开了个店，冰淇淋有 n 个配料， 店里每个配料的 原材料 数量为 wi ，每个 原材料在商店的价格为 vi, 小明有 m 元钱， 问 可以最多做多少冰淇淋
第一种方法 暴力求解 AC 40%
if __name__ == "__main__":
n, m = [int(x) for x in input().strip().split(' ')]
w = [int(x) for x in input().strip().split(' ')]
v = [int(x) for x in input().strip().split(' ')]
cnt = min(w)
for i in range(n):
w[i] -= cnt
while m > 0:
for i in range(n):
if w[i] == 0:
m -= v[i]
else:
w[i] -= 1
cnt += 1
if m == 0:
print(cnt)
else: print(cnt-1) 第二种方法，二分查找
def cost(num, w, v):
price = 0
for i in range(n):
if w[i] > num:
continue
price += v[i]*(num-w[i])
return price
if __name__ == "__main__":
n, m = [int(x) for x in input().strip().split(' ')]
w = [int(x) for x in input().strip().split(' ')]
v = [int(x) for x in input().strip().split(' ')]
l = min(w)
r = 1 + m//sum(v) + max(w)
while l < r:
mid = (l + r + 1) >> 1
if cost(mid, w, v) < m:
l = mid
else:
r = mid-1
print(l) 刚才是写程序 右边界的初始值 有问题， 所以 样例通过70% 现在把代码 改了下 应该通过 100%
#腾讯##笔试题目#
投递完美世界等公司9个岗位 >
