目前我遇到一个问题,我们有两个数组 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
最佳答案
如果您可以计算或估计答案的下限和上限(即结果数组的最小可能最大值),则可以使用二分查找来解决此问题。
为了对答案进行二分查找,我们现在需要一个谓词,我们称它为 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
:
- 如果
xi * yi > val
然后选择一个可能的最小zi
这样xi*yi - zi*yi <= val
- 否则选择最大可能(幅度)
zi
这样xi*yi - zi*yi <= val
仍然是真的
现在,会出现三种情况:
- 如果总和为
zi
是<k
, 然后你可以选择任何一个正zi
并将其增加到总和为zi
的点变成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)
中计算结果
关于algorithm - 在 O(nlog(range of bounds)) 时间内优化列表中的最大值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52730707/