最小化數組中最大值的分配策略

Question

最近，我在解決另一個問題時遇到了這個問題。我自己有一個解決方案。但我對它的時間複雜性並不滿意。所以，我正在轉向你們提供更好的解決方案。問題如下：

假設有一個整數數組int arr[N]。我手裏有一個整數值val，分配給arr。例如，我可以通過val或arr[2]增加arr[0],1和arr[3],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) 

雙減silliness是得到天花板分割。