hdu 5073 Galaxy(数学)

题目链接：hdu 5073 Galaxy

题目大意：给定N个点，可以移动其中的K的点，问说最后I的最小值可以是多少。

解题思路：因为质量都为1嘛，所以就是求方差，可以移动K个，所以即选连续的n=N-K个使得方差最小。注意N=K的情

况。

S表示n个数的和，T表示n个数平方的和，那么这n个数的方差即为T - S * S / n，然后扫描一遍数组维护S，T，并且计算

方差的最小值。

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 50005; const double INF = 1e20; int N, K; double p[maxn]; int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d", &N, &K); for (int i = 1; i <= N; i++) scanf("%lf", &p[i]); if (N == K) { printf("%.10lf\n", 0.0); continue; } sort(p + 1, p + 1 + N); int n = N - K; double s = 0, t = 0; for (int i = 1; i <= n; i++) { t += p[i] * p[i]; s += p[i]; } double ans = t - s * s / n; for (int i = n + 1; i <= N; i++) { t += p[i] * p[i] - p[i-n] * p[i-n]; s += p[i] - p[i-n]; ans = min(ans, t - s * s / n); } printf("%.10lf\n", ans); } return 0; }