python - 无法在均衡群体财富的程序中找到错误 (UVA 10137, "The Trip")

Question

我为 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。我的错误在哪里？

Answer 1

共识似乎是我得到不同答案的原因是我只使用整数运算，而他们的答案使用浮点运算。虽然他们的算法在无限精度上是正确的，但事实证明，在这种情况下，由于奇怪的侥幸， float 的不精确性给出了一个偏差。这是由 gcc 编译代码验证的，它给出了与我的答案不同的答案，但是 clang 编译代码给出了我发现的相同答案。