目前我遇到了一个问题,我们有两个数组,比如x=[x1,x2,x3,...,xn]
数组y=[y1,y2,y3,...,yn]和一个值k。现在我必须从k生成一个数组sayz=[z1,z2,z3,...,zn],这样z1+z2+z3...+zn=k。对于生成的不同z,max的最小值为[(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

最佳答案

如果你可以计算或估计你的答案的下限和上限(这是你得到的数组的最小可能最大值),那么你可以使用二进制搜索来解决这个问题。
为了二进制搜索答案,我们现在需要一个谓词,我们称之为p。
p(val)=cc>如果存在数组true,那么z的最大值小于等于(xi-zi) * yival
为了证明二进制搜索可以使用这个谓词,我们需要证明两件事:
如果false
然后p(a) = true表示所有p(b) = true
如果b >= a
然后p(a) = false表示所有p(b) = false
这两个语句可以用谓词的定义来证明。
要计算给定值的谓词,请尝试估计每个b <= a
如果zi,则选择一个可能的最小值xi * yi > val,以便zi
否则,选择最大可能(大小)xi*yi - zi*yi <= val,这样zi仍然是真的。
现在,将有三个案例:
如果xi*yi - zi*yi <= val的和是zi,则可以选择任何一个正的<k,并将其增加到zi的和变为zi的点。你可以看到,增加这个k不会影响谓词值,因为zi的最大值仍然小于(xi-zi)*yi。在这种情况下,谓词将为true。
如果sum正好k,则再次为true。
如果总和大于k,则结果为false。在这种情况下,不能选择负的k,因为它已经处于允许的最大值,所以可以减少更多。
现在,是时候编写一些代码了。

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

使用此选项,您可以在zi中计算结果。

关于algorithm - 优化O(nlog(边界范围))时间中的列表中的最大值,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52730707/

10-11 03:42