Galaxy
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5073
Mean:
在一条数轴上，有n颗卫星，现在你可以改变k颗卫星的位置，使得剩下的n-k颗卫星到某个点(不固定)的距离的平方和最小。
抽象成数学语言后等价于：数轴上有n个点，现在去掉k个点，使得剩下的n-k个点的方差最小，求方差*n的值。
analyse:
一道让人很容易想偏的数学题。首先说一下我的思路：
1)我们最终的目的是让这n-k个点尽量的集中，所以去掉的这k个点必须是位于两边的点(想不通的请自行补脑);
2)剩下的事情就是枚举两边的数量了，但是在枚举这一步，怎样才不超时呢?咳咳，这题的关键来了。
我们可以先来推一下公式：
设Fn为这n个数的方差，d为这n个数的平均数，那么:
Fn=[(x1-d)^2+(x2-d)^2+......(xn-d)^2]/n;
=[sum(xi^2)+n*d*d-2*d*sum(xi)]/n;
根据这个公式来枚举前后个数就简单多了，详见代码。
Time complexity: O(n)
Source code:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-11-16-22.59
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define LL long long
using namespace std;
#define N 50000+10
double a[N],sum1[N],sum2[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
memset(sum1,0,sizeof sum1);
memset(sum2,0,sizeof sum2);
double tmp1,tmp2;
tmp1=tmp2=0.0;
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)
{
sum1[i]=sum1[i-1]+a[i];
sum2[i]=sum2[i-1]+a[i]*a[i];
}
if(n==k)
{
puts("0.0000000000000");
continue;
}
int m=n-k; /**< 需要选的人数 */
double d;
double tmp;
int sta,en;
double res=1000000000000000000.0;
// cout<<setprecision(10)<<res<<endl;
for(int i=1;i+m-1<=n;++i)
{
sta=i;
en=i+m-1;
d=(sum1[en]-sum1[sta-1])/m;
tmp=(sum2[en]-sum2[sta-1])+m*d*d-2*d*(sum1[en]-sum1[sta-1]);
if(tmp<res)
{
res=tmp;
}
}
printf("%.9lf\n",res);
}
return 0;
}