求助,python,只过了样例,pts 0
查看原帖
求助,python,只过了样例,pts 0
493638
隐公元年楼主2022/10/30 23:14

思路和大家应该是差不多的,优先选择性价比高的那一组金币,在此基础上,背包还有多大空间,就对他取多大空间的数量,也注意到了排序过程中直接使用double会造成的精度问题,我还尝试用了python的decimal模块,让实数的精度设置成了20,然后对他排序,也一分没有

def SolutionP2240(n, t, m, v):
    def cmp(a, b):
        return a[0] * b[1] - b[0] * a[1]

    from functools import cmp_to_key

    li = sorted(list(zip(m, v)), key=cmp_to_key(cmp))

    ans, cnt = 0, 0
    while t > 0 and cnt < len(m):
        use = min(t, m[cnt])  # 对于第cnt中金币有多少空间取多少空间
        t -= use
        ans += use * li[cnt][1] / li[cnt][0]
        cnt += 1

    return '%.2f' % (ans)


n, t = map(int, input().split())
m, v = [], []
for i in range(n):
    a, b = map(int, input().split())
    m.append(a)
    v.append(b)
print(SolutionP2240(n, t, m, v), end='')
2022/10/30 23:14
加载中...