谦卑计数课

Question

我正在学习谦逊计数课(https://codility.com/media/train/2-CountingElements.pdf)，我需要帮助来理解最快的解决方案。

我想知道为什么第8行d //= 2中的差异被2除以2？这种差异难道不足以找到我们可以在数组之间交换的元素吗？

问题是：

给您一个整数m (1 < m < 1000000)和两个非空的零索引数组A和B of n整数、a0、a1、.、an−1和b0、b1、.、bn−1 (0 < ai、bi < m)。目的是检查是否存在可以对这些数组执行的交换操作，使数组A中的元素之和等于交换后数组B中的元素之和。交换操作意味着从数组A中选择一个元素，从数组B中选择一个元素并进行交换。

解决办法：

 def fast_solution(A, B, m):
   n = len(A)
   sum_a = sum(A)
   sum_b = sum(B)
   d = sum_b - sum_a
   if d % 2 == 1:
       return False
   d //= 2
   count = counting(A, m)
   for i in xrange(n):
       if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
           return True
   return False

Answer 1

A[i]和B[j]之间的交换将B[j]-A[i]添加到sum(A)中，从sum(B)中减去相同的值；因此，它会影响两次 B[j]-A[i]的和差。

因此，将原来的差异减半是正确的(在检查它是偶数之后--如果是奇数，则没有交换将有效！-)以构成可能的交换的目标。

还请注意，它们提供的counting函数并不是现代Python的最佳功能--为了避免重新发明“计数项”的特定轮子，请参阅https://docs.python.org/2/library/collections.html#collections.Counter for Python2或https://docs.python.org/3/library/collections.html#collections.Counter for Python3。

Answer 2

让Ea = a0 + a1 + .. + a(n-1)。让Eb = b0 + b1 + .. + b(n-1)。然后交换元素ai和bj将对这些和产生以下影响：Ea - ai + bj、Eb + ai - bj。根据问题描述，那么这些和应该相等，所以Ea - ai + bj = Eb + ai - bj，让我们指定d = bj - ai。然后我们有以下等式：Ea + d = Eb - d，它给我们2d = Eb - Ea或d = (Eb - Ea)/2。关于(Eb - Ea)是奇数的情况，请参阅Alex的comment。

唯一剩下的就是找到这样的bj和ai，以便bj - ai = d。