在一个平衡群体财富的计划中不可能找到错误(UVA 10137,"旅行")

Question

我为这个竞争性编程问题写了一个解决方案.它通过了所有测试用例,除了最后一个案例关闭了一个,我无法弄清楚原因.这个问题可以这样说:假设一个群体中每个人有多少便士,有多少钱可以转手,这样群体中的每个人都会在财富中彼此相差一分钱？

我的程序很简单.我修改它只是操作一个每个人有多少便士的数组:

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

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