首页 > 代码库 > hdu5073 贪心
hdu5073 贪心
这题说的是给了 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;}
hdu5073 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。