大家好，又见面了，我是全栈君。
题目链接：题意：给定一条线上的点，然后能够去掉当中的m个，使剩下的到重心的距离最小，
因为重心等于距离的平均值。因此也就是求方差最小。
分析：
由于要去掉m个所以一定剩下n-m个，我们枚举这一串点的起始位置从1開始 一直枚举到m，
然后由平方和的公式展开。预处理一下前几项平方和。以及前几项的和就可以，复杂度为O(N);
代码例如以下：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 50010;
long long a[maxn];
int main()
{
int n,m,t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
if(n==m){
printf("0\n");
continue;
}
sort(a+1,a+n+1);
long long sum1=0,sum2=0;
for(int i=1;i<=n-m;i++){
sum1+=a[i];
sum2+=a[i]*a[i];
}
double mess = sum1*1.0/(n-m);
double ans = sum2 + (n-m)*mess*mess - 2*sum1*mess;
for(int i=1;i<=m;i++){
sum1 = sum1-a[i]+a[n-m+i];
sum2 = sum2 - a[i]*a[i]+a[n-m+i]*a[n-m+i];
mess = sum1*1.0/(n-m);
ans = min(ans,sum2 + (n-m)*mess*mess - 2*sum1*mess);
}
printf("%.10lf\n",ans);
}
return 0;
}
/***
100
3 2
-1 0 1
4 2
-2 -1 1 2
****/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116641.html原文链接：https://javaforall.net
