给定一个数组arr和一个整数x，分配x使任意对之间的差值尽可能最小。
。arr= [4,2,0] andx= 10;
答案应为[6,5,5];
必须使用所有x
计算最终均值为(sum(arr) + x) / len(arr)。这将是所有数字的理想目标，如果我们也可以减少。
四舍五入商告诉我们每个数字的最小值，余数告诉我们有多少个数字可以再加一个1。在去掉已经太大的数字后再做。
总时间O(n log n).
Python实现:
def distribute(arr, x):
total = sum(arr) + x
I = sorted(range(len(arr)), key=arr.__getitem__)
while I:
minimum, additional = divmod(total, len(I))
if arr[I[-1]] <= minimum:
break
total -= arr[I.pop()]
for i in sorted(I):
arr[i] = minimum
if additional > 0:
arr[i] += 1
additional -= 1
测试一些硬编码输入、较大随机输入和穷举小输入的结果:
433103 tests passed
0 tests failed
完整代码(在线试用!):
from random import choices
from itertools import product
def distribute(arr, x):
total = sum(arr) + x
I = sorted(range(len(arr)), key=arr.__getitem__)
while I:
minimum, additional = divmod(total, len(I))
if arr[I[-1]] <= minimum:
break
total -= arr[I.pop()]
for i in sorted(I):
arr[i] = minimum
if additional > 0:
arr[i] += 1
additional -= 1
def naive(arr, x):
for _ in range(x):
arr[arr.index(min(arr))] += 1
passed = failed = 0
def test(arr, x):
expect = arr.copy()
naive(expect, x)
result = arr.copy()
distribute(result, x)
global passed, failed
if result == expect:
passed += 1
else:
failed += 1
print('failed:')
print(f'{arr = }')
print(f'{expect = }')
print(f'{result = }')
print()
# Tests from OP, me, and David
test([4, 2, 0], 10)
test([4, 2, 99, 0], 10)
test([20, 15, 10, 5, 0], 10)
# Random larger tests
for x in range(1000):
arr = choices(range(100), k=100)
test(arr, x)
# Exhaustive smaller tests
for n in range(5):
for arr in product(range(10), repeat=n):
arr = list(arr)
for x in range(n * 10):
test(arr, x)
print(f'{passed} tests passed')
print(f'{failed} tests failed')
对于范围较小的大输入，二分搜索目标最小值可以更有效。我没有预料到这一点，但很明显，即使对于中等规模的范围，这个解决方案也可以比"不要只讲代码"的答案快7倍。下面是一个范围为20(快7倍)和100,000,000(快2倍)的示例:https://ideone.com/X6GxFD。当我们增加输入长度时，即使对于整个64位范围，这个答案似乎也要快得多。
Python代码:
def f(A, x):
smallest = min(A)
lo = smallest
hi = smallest + x
while lo < hi:
mid = lo + (hi - lo) // 2
can_reach = True
temp = x
for a in A:
if a <= mid:
diff = mid - a
if diff > temp:
can_reach = False
break
else:
temp -= diff
if can_reach:
lo = mid + 1
else:
hi = mid
target = lo - 1
for i, a in enumerate(A):
if a < target:
x -= target - a
A[i] = target
if x:
for i, a in enumerate(A):
if a == target:
A[i] += 1
x -= 1
if x == 0:
break
return A
这里有一个解决方案，可以击败我的二进制搜索答案，以及不要只谈论一些较大输入长度的代码答案。其思想是对数组进行排序，并通过累加找到最大的最小值，从小到大遍历，后者使用O(1)空间，避免弹出操作。
测试链接。Python代码:
def g(A, x):
s = sorted(range(len(A)), key=lambda i: A[i])
total = x
count = 1
curr = A[s[0]]
to_add = 0
extra = 0
for i in range(1, len(A)):
diff = A[s[i]] - curr
needed = count * diff
if needed >= total:
break
curr = A[s[i]]
total -= needed
count += 1
if total:
extra, to_add = divmod(total, count)
for i in range(count):
A[s[i]] = curr + extra
if to_add:
A[s[i]] += 1
to_add -= 1
return A
假设未更改值的位置不需要保留:
- 转换为最小堆("heapify"， O(n))
- repeat pop&从堆中计算最小值，直到
- empty: distribute rest: done -or-
- top更大;- 如果剩余值不足以使所有最小值等于top，则分配rest: done
O(n+# increed_values *log(n))
最后回写增加的值作为练习(目前)。
假设您要最小化任何对数字之间的最大差值，那么一般方法是:
- 对数字排序
- 查找最低数量
- 如果有Y个最低数字，则X减Y，并对每个最低数字加1，直到X耗尽，或者最低数字等于下一个最低数字， 如果没有，那么就重复步骤#2。
显然，你可以用一点数学来改进步骤#3。