algorithm - 最大化对由值界定的排序数组的总和做出贡献的因素数

Question

我有一个大小为 n 的有序整数数组。这些值不是唯一的。我需要做的是: 给定一个 B，我需要找到一个 i<A[n]这样 |A[j:1 to n]-i| 的总和小于 B 并且对那个特定的总和贡献最大数量的 A[j]。我有一些想法，但我似乎无法从朴素的 n*B 和 n*n 算法中找到更好的东西。关于 O(nlogn) 或 O(n) 的任何想法？例如:想象一下

A[n] = 1 2 10 10 12 14 and B<7 then the best i is 12 cause I achieve having 4 A[j]s contribute to my sum. 10 and 11 are also equally good i's cause if i=10 I got 10 - 10 + 10 - 10 +12-10 + 14-10 = 6<7

Answer 1

复杂度为 O(n) 的解决方案:从末尾开始计算 a[n]-a[n-1]:让 d=14-12 => d=2 和 r=B-d => r=5,然后重复操作，但将 d 乘以 2:d=12-10 => d=2 和 r=r-2*d => r=1,r=1 算法结束，因为和必须小于 B:

索引为 0..n-1 的数组

i=1
r=B
while(r>0 && n-i>1) {
  d=a[n-i]-a[n-i-1];
  r-=i*d;
  i++;
}
return a[n-i+1];

也许一张图解释得更好

14       x
13       x  -> 2
12      xx
11      xx  -> 2*2
10    xxxx    -> 3*0
 9    xxxx   
 8    xxxx
 7    xxxx
 6    xxxx
 5    xxxx
 4   xxxxx
 3   xxxxx
 2  xxxxxx
 1 xxxxxxx