hdu 5073 Galaxy

题意是给定n个点,让求找到一个点p使得sigma( (a[i] - p) ^ 2 ) 最小,其中a[i]表示第i个点的位置。其中有k个点不用算。

思路:发现这道题其实就是求n-k个点方差。

那么推一下公式就是:

sigma( (a[i] - p)^ 2 )

= sigma( a[i]^2 + p^2 - 2*a[i]*p )

= sigma( a[i]^2 + p^2) ) - sigma( 2*a[i]*p )

= sigma( a[i]^2 ) + (n-k)*(p^2) - 2*p*sigma( a[i] ) //因为sigma求的是n-k个数的和

= sum2[i] + (n-k)*(p^2) - 2*p*sum[i]

这里sum2[i]就是前个数的平方和,sum[i]是前i个数的和。p是这段长度为n-k的区间的平均值。一遍预处理就可以求出来。所以总的时间复杂度也是O(n)

原文地址:https://www.cnblogs.com/Howe-Young/p/4943495.html