8/17腾讯笔试-原料做冰淇淋题讨论

题目

做冰淇淋需要 n 种原料，现每种原料有存货 W = [w1, w2, ...] 个，对应的价格 V = [v1, v2, ...]
存货用完就需要去商店买，现共有钱 M 元。
问，总共能做多少冰淇淋。

思考

大概思想是，先按存货的个数排序，再每次买后一个与前一个的差值*当前总价（如果买得起，否则能买多少买多少）。同时当前买东西的总价要滚动增加。
其中注意存货相等的物料特殊处理。

自己试了几个用例都能过。不知道哪里还有问题。

def fun(W, V, M):
    map =list(zip(W, V))
    map = sorted(map, key=lambda x: (x[0], x[1]))  # 先按个数排序，再按价格排序
    W = [x[0] for x in map]
    V = [x[1] for x in map]
    res = W[0]  # 最少能做的个数
    curSum = V[0]  # 当前总价
    i = 0
    while i <= len(W) - 2:  # 遍历到倒数第二个元素位置
        while W[i+1] == W[i]: # 若与后面的存货相等，则要将后面的价格加入curSum
            curSum += V[i + 1]
            i += 1
            if i == len(W) - 1:  # 若已经遍历到最后一个了，说明后面的所有存货都相等了。直接统一计算即可。
                res += M // curSum
                return res
        if M - curSum * (W[i + 1] - W[i]) >= 0:  # 如果买得起就买
            res += W[i+1] - W[i]
            M -= curSum * (W[i + 1] - W[i])
        else:  # 否则能买多少买多少
            res += M // curSum
        curSum += V[i + 1]  # 滚动增加当前总价
        i += 1
    # 若存货已全部消耗完时，还有余额，则所有统一购买。
    res += M // curSum
    return res

W = [5, 5, 5]
V = [2, 1, 3]
m = 10
print(fun(W, V, m))