algorithm - 最小化数组中最大值的分布策略

Question

最近，我在解决另一个问题时遇到了这个问题。我自己有解决办法。但是我对它的时间复杂度不是很满意。所以，我向你们寻求可能更好的解决方案。问题如下:

假设有一个整数数组int arr[N]。我手头有一个整数值val要分配给arr。例如，我可以将 arr[0] 增加 val，或者将 arr[2] 增加 1 和 arr[3] by val - 1，依此类推。目标是在分配后最小化 arr 中的最大值。可能有多种解决方案，任何人都会这样做。

我目前的解决方案如下。这很简单，需要 O(val) 时间。我感觉存在更好的解决方案。

for (int i = 0; i < val; ++i) {
  // increase the minimum value in arr by 1
}

Answer 1

这是一个线性时间算法。首先尝试将所有内容增加到当前最大值。如果我们必须继续前进，请尽可能均匀地分配其余部分。在未经测试的 Python 中:

def distribute(arr, val):
    maxarr = max(arr)
    for x in arr:
        val -= min(maxarr - x, val)
    return maxarr - (-val) // len(arr)

double minus sillness 是为了得到 ceiling division.