在 O(nlog(range of bounds)) 时间内优化列表中的最大值

Question

目前我遇到了一个问题，我们有两个数组 x=[x1,x2,x3,...,xn] 和数组 y=[y1,y2,y3,...,yn] 和一个值 k。现在我必须从 k 生成一个数组 z=[z1,z2,z3,...,zn] ，这样 z1+z2+z3...+zn=k 。对于不同的 z 生成什么将是 [(x1-z1)*y1, (x2-z2)*y2, (x3-z3)*y3, ...., (xn-zn)*yn] 的最大值的最小值。即 (x[i]-z[i])*y[i] 的最大值的最小值。例如如果 x=[2,3,4,1,6] 和 y=[3,5,2,7,3] 和 k=4 而不是采用 z=[0,1,0,0,3] 给出数组 [6,10,8,7,9]，其最大值为 10，这也是最小最大值。
我设计了一个在 O(nlog(n)+k) 中计算它的算法。这里如果 k 非常大，我的算法将效率低下。我们可以在 O(n) 或 O(nlog(n)) 中完成吗？我当前的算法是：

1. l=[] //initialize empty array
2. for i from 0 to n:
     l.append(x[i]*y[i],y[i])
3. Sort l in decreasing order of (x[i]*y[i])
4. while(m>0):
     num=l[0][0]-l[1][0] //take difference of two largest x[i]*y[i]
     t=(num/l[0][1])+1 //Choose appropriate number to subtract to minimize 
                         the maximum
     t=max(0,t)        // t must not be negative
     l[0][0]=l[0][0]-t*l[0][1]
     Put l[0] at correct position in sorted list l //Since value of 
                                                     l[0][0] has 
                                                     changed we will 
                                                     place it at 
                                                     correct position 
                                                     in already sorted  
                                                     l (using binary 
                                                     search)
     m=m-t
5.Print l[0][0] as the minimum maximum

Answer 1

如果您可以计算或估计答案的下限和上限（即结果数组的最小可能最大值），则可以使用二分查找来解决此问题。

要对答案进行二分查找，我们现在需要一个谓词，我们称它为 p。

p(val) = true 如果存在数组 z 使得 (xi-zi) * yi 的最大值小于等于 val 且 false否则

为了证明二分查找可以使用这个谓词工作，我们需要证明两件事：

如果p(a) = true 然后 p(b) = true 所有 b >= a
如果p(a) = false 然后 p(b) = false 所有 b <= a

这两个命题可以用谓词的定义来证明。

要评估给定值的谓词，请尝试估计每个 zi:

if xi * yi > val 然后选择一个可能的最小值 zi 这样 xi*yi - zi*yi <= val
否则选择最大可能（量级）zi 使得 xi*yi - zi*yi <= val 仍然为真

现在，会出现三种情况：

如果 zi 的总和是 <k，那么你可以 select 任何正数 zi 并将其增加到 [=23= 的总和的点] 变成 k。您可以看到增加此 zi 不会影响谓词值，因为 (xi-zi)*yi 的最大值仍然小于 k。在这种情况下谓词将为真。
如果总和恰好 k，则再次为真。
如果总和大于k则结果为假。在这种情况下，不能选择负数 zi 并减少更多，因为它已经处于允许的最大值。

现在，是时候编写一些代码了。

low = -100
high = 100 # these two are assumed values

x = [2, 3, 7, 1, 6]
y = [3, 5, 2, 7, 3]
k = 4

def p(val):
    sum_zi = 0  # sum of possible zi
    for idx in range(len(x)):
        if x[idx]*y[idx] > val:
            diff = x[idx]*y[idx] - val
            zi = (diff + y[idx] - 1) // y[idx]
            sum_zi += zi
        else:
            diff = x[idx]*y[idx] - val
            zi = diff // y[idx]
            sum_zi += zi
    return sum_zi <= k

while low < high:
    mid = (low + high)//2
    if p(mid):
        high = mid
    else:
        low = mid+1

print("Min possible max value", low)
# output = 10

使用这个你可以在nlog(range of bounds)

中计算你的结果

在 O(nlog(range of bounds)) 时间内优化列表中的最大值

Optimising the maximum value in a list in O(nlog(range of bounds)) time

algorithm

complexity-theory

combinatorics

minimization

greedy