如何将固定数量添加到高度数组中，以使新的最小值均匀分布？ [英] How to add a fixed amount to an array of heights so that the new minimums spread evenly?

问题描述

给出一个高度数组 H 和一个金额 A ，什么是最好的分配方式 A 在 H 之间以最大化最小数组值。

Given an array of heights, H, and an amount, A, what is the best way to distribute A between H to maximize the minimum array value.

示例1：

H = {1，3，2，2，4}

A = 4

输出= {3 ，3、3、3、4}

Example2：

H = {1，3，2，2，4}

A = 3

输出= {2.66，3，2.66，2.66，4}

推荐答案

O（N ^ 2）中的简单算法：

sort(T) // In ascending order; O(N log(N))

while amount > 0:
    i := first index such that T[i] < T[i+1]   # O(log(N)) at worst if you look for it from scratch each time, or (better) in average O(1) if you keep track of the previous such i and just look at the next values like  @jdehesa does
    amount_to_add := min(T[i+1] - T[i], amount / i)  # Considering that T[N] = infinity  makes it useless to do another loop if amount is big, it's all included here
    for j <= i:
        T[j] += amount_to_add 
    amount -= i * amount_to_add

在最坏的情况下，您将看到i的每个位置一次，并进行长度为i的循环，因此 O（N ^ 2） 。

At worst you'll see each position for i once, and do a loop of length i, hence O(N^2).

通过存储，您实际上可以达到 O（Nlog（N））您必须在第一个循环中执行的更改，然后在第二个循环中执行更新：

You can actually reach O(Nlog(N)) by just storing the changes you'll have to do in a first loop, and performing the updates in a second loop:

sort(T) # In ascending order; O(N log(N))

lowest_value := T[0]
amount_to_add := zeros(N)  # Array containing zeros initially
while amount > 0:
    i := first index such that lowest_value < T[i+1]   # O(log(N)) at worst. In practice probably O(1) if you keep track of the previous such i
    amount_to_add[i] := min(T[i+1] - lowest_value, amount / i) # Considering that T[N] = infinity  makes it useless to do another loop if amount is big, it's all included here
    lowest_value +=  amount_to_add[i]
    amount -= i * amount_to_add[i]
amount_to_add_incremental = 0
for j=N-1 to 0:
    amount_to_add_incremental += amount_to_add[j]
    T[j] += amount_to_add += amount_to_add_incremental 

也许有更好的东西可以有效地计算 O（N）中的最终值，然后更新其中的所有元素数组，在这种情况下，您可以获得 O（N），但是您做得不会更好。

Maybe there is something better that can efficiently compute the final value in O(N) and then update all elements in the array, in which case you could get O(N), but you won't do better than that.

例如，如果您假设金额大：如果金额> = N * max（T）-sum（T）例如，只需花费 O（N）时间即可检查，那么您可以直接设置所有将T中的值更改为 max（T）+（金额-N * max（T）+ sum（T））/ N ，则需要 O（ N）时间。 金额较小的情况更有问题。

For instance if you assume that amount is big: if amount >= N*max(T) - sum(T) for instance, which only takes O(N) time to check, then you can directly set all values in T to max(T) + (amount - N*max(T) + sum(T))/N, it takes O(N) time. The case where amount is smaller is more problematic.

这篇关于如何将固定数量添加到高度数组中，以使新的最小值均匀分布？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！