algorithm - 删除连续子数组以保留平均最小值

Question

这个问题出现在一些ICPC的区域竞赛中。

给定 n 个数字，您必须删除 i 到 j 之间的数字，使剩余数字的平均值最小。您不能删除第一个和最后一个数字。

2 <= n <= 10^5

我们对此进行了讨论，但我仍然无法理解。一些如何将此问题转换为查找具有最大和的连续子数组，然后在 O(nlog n) 中使用二进制搜索解决的问题。

我在讨论时无法理解该解决方案，现在经过大量思考后我无法理解该解决方案。

链接到原始问题以防不清楚:http://programmingteam.cc.gatech.edu/contest/Mercer14/problems/6.pdf

Answer 1

我认为这是一种可行的方法:

• 从左开始计算所有元素的部分平均值，并更新平均值，这可以在 O(N) 中完成:a_L(i) = (a_L(i-1)*(i-1) + a_L(i))/i

• 对右侧的部分平均值执行相同操作:a_R(i) = (a_R(i+1)*(N-i) + a_R(i))/(N-i+1)

• 找到两个列表中的最小值。

• 如果最小值在左侧部分平均值 (a_L) 中，则在 a_R 中寻找它右侧的最小值，如果在 a_R 中找到最小值，则反之。

所有部分都需要 O(N)。因此，这将导致 O(N) 算法。不过，这听起来有点简单，我可能会遗漏一些东西。

编辑:原来的答案在两个列表的中间都停了下来，再想想这是不够的。

实际上，如果最小值重叠，我相信，没有间隔可以切掉。下面是该算法的一些 Python 实现:

grades = [5, 5, 1, 7, 8, 2]

N = len(grades)
glob_avg = float(sum(grades))/float(N)
print('total average: {0}'.format(glob_avg))

avg_L = grades[:]
avg_R = grades[:]

minL = 0
minR = N-1

for i in range(1,N):
  avg_L[i] = float(avg_L[i-1]*i + grades[i])/float(i+1)
  if avg_L[i] <= avg_L[minL]:
    minL = i
  avg_R[N-i-1] = float(avg_R[N-i]*i + grades[N-i-1])/float(i+1)
  if avg_R[N-i-1] <= avg_R[minR]:
    minR = N-i-1

opti_avg = glob_avg
if minL < minR:
  first = minL+1
  last = minR
  opti_avg = (avg_L[first-1]*first + avg_R[last]*(N-last)) / float(N + first - last)
  print('')
  print('Interval to cut: {0} - {1}'.format(first,last))
  for pre in grades[:first]:
    print('{0}'.format(pre))
  for cut in grades[first:last]:
    print('X {0} X'.format(cut))
  for post in grades[last:]:
    print('{0}'.format(post))

else:
  print('NO interval found that would reduce the avg!')

print('')
print('--------------------------------------')
print('minimal avg: {0:0.3f}'.format(opti_avg))
print('--------------------------------------')