目前我遇到了一个问题，我们有两个数组说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)