arrays - 修改数组以最小化差异

Question

给定一个包含n 个值的数组A 和一个值k。您必须将 A 中的每个元素增加或减少 k，并且必须对每个元素只做一次。目标是最小化结果数组 A(修改后)中最大和最小元素之间的差异，并输出此差异。

例如A=[1,7]，k=4，我们需要将A修改为[5 ,3]，那么差就是2，这是我们能达到的最小差。

谁能帮我解决这个问题？

Answer 1

这是一种思考方式(想象一个排序数组，x 是 a[i] + k 和 y 是 a[i] - k )

x
  x
      x
           x
y              
  y             x[i](min?)
      y                   x
           y                  x[n-1]
                y[i](min?)     
                          y   
                              y 

如果选择y[i]作为最小值，您对最大值的选择是:

max( y[0], x[i + 1] )

如果你选择 x[i]作为最低限度......哦你不能因为任何a[j] ± k, j > i在这种排序排列中必须更小。

如果选择x[n-1]作为最小值，您对最大值的选择将是所有 min(x[j],y[j]) where both x[j] and y[j] are greater than or equal to x[n-1] (or just x[j] if y[j] < x[n-1]) 中最大的一个.

如果选择y[0]作为最小值，您选择的最大值为 max(x[j]) , 前提是所有 x[j]大于或等于 y[0] .