最近，我在解决另一个问题时遇到了这个问题。我自己有一个解决方案。但是我对其时间的复杂性并不满意。因此，我正在寻求你们提供更好的解决方案。问题如下：
假设有一个整数数组int arr[N]。我的val手中有一个整数值要分配给arr。例如，我可以增加arr[0]通过val，或arr[2]通过1和arr[3]通过val - 1，等等。目的是使arr分配后的最大值最小化。可能有多种解决方案，任何人都可以做。
我当前的解决方案如下。这很琐碎，需要O(val)时间。我有更好的解决方案。
for (int i = 0; i < val; ++i) {
// increase the minimum value in arr by 1
}
这是线性时间算法。首先尝试将所有内容增加到当前的最大值。如果我们必须继续前进，请尽可能均匀地分配其余部分。在未经测试的Python中：
def distribute(arr, val):
maxarr = max(arr)
for x in arr:
val -= min(maxarr - x, val)
return maxarr - (-val) // len(arr)
减负的两倍是为了划分天花板。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句