首页 > 代码库 > hdu5073 贪心

hdu5073 贪心

2024-07-29 05:45:55   220人阅读

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

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

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int maxn = 50005;double A[maxn];int main(){    int cas;    scanf("%d",&cas);    for(int cc=1; cc<=cas; ++cc){         int n,k;         scanf("%d%d",&n,&k);         for(int i=0; i<n; ++i)             scanf("%lf",&A[i]);         sort(A,A+n);         double square=0,dec=0,x=0;         if(n==k){             printf("0\n"); continue;         }         int sz=n-k;         for(int i=0; i<sz; ++i){             square+= A[i]*A[i];             dec+=2*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-=2*A[i-sz];              dec+=2*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 0;}
View Code

 

hdu5073 贪心


联系
我们