我为 this competitive programming problem 写了一个解决方案.它通过了所有测试用例,除了最后一个测试用例差了一个,我不明白为什么。问题可以这样表述:给定一个群体中每个人有多少便士,需要转手多少钱才能使该群体中的每个人的财富相差在一便士以内?
我的程序很简单。我将其修改为仅对每个人拥有多少便士的数组进行操作:
def transfer(A):
A.sort(key = lambda x:-x)
extra = sum(A) % len(A)
average = sum(A) // len(A)
high = sum([abs(x - (average+1)) for x in A[:extra]])
low = sum([abs(x - average) for x in A[extra:]])
return (high+low)/2
失败的测试用例如下:
print(transfer([613, 944, 7845, 8908, 12312, 22378, 27877, 54757, 55476, 90707, 91289, 178189]))
我的代码显示答案是 240710
,而“正确”答案是 240709
。我的错误在哪里?
最佳答案
共识似乎是我得到不同答案的原因是我只使用整数运算,而他们的答案使用浮点运算。虽然他们的算法在无限精度上是正确的,但事实证明,在这种情况下,由于奇怪的侥幸, float 的不精确性给出了一个偏差。这是由 gcc
编译代码验证的,它给出了与我的答案不同的答案,但是 clang
编译代码给出了我发现的相同答案。
关于python - 无法在均衡群体财富的程序中找到错误 (UVA 10137, "The Trip"),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42193577/