设i开头的子序列中,产生最小平均值的序列结尾下标为x[i]。
那么考虑x[i]确定之后的情况。a[i-1]如果比(i,x[i])的平均值小,那么x[i-1] = i-1。反之如果大于(i,x[i]),那么显然应把x[i]赋值于x[i-1]。
但是仍然有问题。考虑10,2,3,2的情况。设下标为1-4。x[4] = 4,x[3]=4,x[2]=2,x[1]=2。但是实际情况中,x[1]=4。为何?因为除了(2,2)能降低1的平均值外,(3,4)也能降低1开头序列的平均值。而且很容易得到如(2,2)(3,4)这样的一个阶梯型上升队列(j,x[j]),只要比较a[i-1]和(j,x[j])的平均值就可以判断是否需要继续迭代。
#include......
阅读全文