题意:给定(n(n<=50000))个星星所在的位置,可以移动k个星星,一个位置上可以有多个星星,最小化(I=sum_{i=1}^nd_i^2),(d_i)是星星i到中心的距离.
本题难度在于读题,看到上面这个题意还是不太好理解.但我们先分析一下,移动的k个星星我们可以不再考虑,因为我们直接把它们都移到中心位置上,产生的贡献全部为零.然后解释一下这个中心其实就是平均数的意思.
于是题目转化成了,在n个数中选出(n-k)个数,设这(n-k)个数的平均数为(ave),最小化(ans=sum_{i=1}^{n-k}(a[i]-ave)^2).
我们把上式拆开,得到(ans=(sum_{i=1}^{n-k}a[i]^2)-(2*ave*sum_{i=1}^{n-k}a[i])+(n-k)*ave^2).
因为我们选出的n-k个数一定是连续的才会是最优的,所以我们一开始就把这n个数从小到大排序,然后可以预处理出(a[i])和(a[i]^2)的前缀和数组,接下来就可以每次(O(1))计算更新答案了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=50005;
int a[N];ll sum1[N],sum2[N];
int main(){
int T=read();
while(T--){
int n=read(),k=read(),m=n-k;
for(int i=1;i<=n;++i)a[i]=read();
if(!m){puts("0");continue;}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)sum1[i]=sum1[i-1]+a[i],sum2[i]=sum2[i-1]+1ll*a[i]*a[i];
double ans=1e18;
for(int i=1;i<=k+1;++i){
int j=i+m-1;
double x=1.0*(sum1[j]-sum1[i-1])/m;
ans=min(ans,sum2[j]-sum2[i-1]+1.0*m*x*x-2.0*(sum1[j]-sum1[i-1])*x);
}
printf("%.9lf
",ans);
}
return 0;
}