hdu5073 贪心

这题说的是给了 n个值每个值 然后 他们的品均值 作为中点 然后每个点到中点的均值的平方 和最小值是多少

有 k 个点可以重新 放过位置 ， 这样我们 应该 会选 最近的那个 n-k个点 然后 取他们的均值点  这样我们只要先排序 排完后 直接 遍历过去

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = ;

double A[maxn];

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; ++cc){

         int n,k;

         scanf("%d%d",&n,&k);

         for(int i=; i<n; ++i)

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

         sort(A,A+n);

         double square=,dec=,x=;

         if(n==k){

             printf("0\n"); continue;

         }

         int sz=n-k;

         for(int i=; i<sz; ++i){

             square+= A[i]*A[i];

             dec+=*A[i];

             x+=A[i];

         }

         double loc=x/sz;

         double ans = -dec*loc + square + loc*loc*sz;

         for(int i=sz; i<n; ++i){

             square-=A[i-sz]*A[i-sz];

             square+=A[i]*A[i];

              dec-=*A[i-sz];

              dec+=*A[i];

              x-=A[i-sz];

              x+=A[i];

              loc=x/sz;

             ans=min(ans,-dec*loc + square + loc*loc*sz);

         }

         printf("%lf\n",ans);

    }

    return ;

}