hdu 5073 Galaxy(數學)

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;
}