hdu 5073

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5073

思路：一开始忘了排序，wa了好几发。。。选择区间长度为N - K的连续的数， 然后其余的K个数都移动到这N-K个数的中心就可以，公式为ans = min(ans, pos[i] - center_point) ^ 2），把这个公式展开然后预处理一下就可以了，复杂度为O(N)。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int MAX_N = (50000 + 5000);

int N, K;

double pos[MAX_N], sum1[MAX_N], sum2[MAX_N];

int main()

{

    int cas;

    scanf("%d", &cas);

    while (cas--) {

        scanf("%d %d", &N, &K);

        for (int i = 1; i <= N; ++i) {

            scanf("%lf", &pos[i]);

        }

        if (N == K) {

            puts("0");

            continue;

        }

        sort(pos + 1, pos + 1 + N);

        sum1[0] = sum2[0] = 0;

        for (int i = 1; i <= N; ++i) {

            sum1[i] = sum1[i - 1] + pos[i];

            sum2[i] = sum2[i - 1] + pos[i] * pos[i];

        }

        double ans = 1e100, point_b = 0;

        int M = N - K;

        for (int i = M; i <= N; ++i) {

            point_b = (sum1[i] - sum1[i - M]) / M;

            double tmp = (sum2[i] - sum2[i - M])  - 2 * point_b * (sum1[i] - sum1[i - M]) + M * point_b * point_b;

            ans = min(ans, tmp);

        }

        printf("%.12f\n", ans);

    }

    return 0;

}