题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5073
解题报告:在一条直线上有n颗星星,一开始这n颗星星绕着重心转,现在我们可以把其中的任意k颗星星移动到这条直线上的任意位置然后围绕这个新的重心转, 这个星系的惯性值I = w1 * d1^2 + w2 * d2 ^ 2 +......+wn * dn ^ 2,其中wi表示第i颗星星的重量,di表示第i颗星星到这个星系的重心的距离.然后现在要你求转移k颗星星之后惯性值最小是多少?
n颗星星转移k颗后还剩下n-k颗是不能移动的,很显然转移的k颗星星一定是转移到重心的位置,然后每颗星星的重量都是1,所以求I时就可以不用管wi了,然后我们可以枚举n-k个星星所在的区间,而且可以确定这n-1个星星在位置上一定是连续的.然后枚举出了k个区间,怎么能在O(1)时间算出每个区间的I值呢?作如下转化(其中e表示重心的坐标):
(x1-e)^2 + (x2-e)^2 (x3-e)^2+....(xn-e)^2
=x1^2 + x2^2+...xn^2 + n * e^2 - 2*e*(x1+x2+x3+...xn)
这样通过预先求出x1的平方到xn的平方的和还有x1到xn的和就可以在O(1)时间内求出Ｉ的值了.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = ;
const double eps = 1e-; int T,n,k;
double pos[maxn],sump[maxn],sump2[maxn];
int main()
{
// freopen("in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i = ;i <= n;++i)
scanf("%lf",&pos[i]);
sort(pos+,pos+n+);
sump[] = sump[] = sump2[] = sump2[] = ;
for(int i = ;i <= n;++i)
{
sump[i] = sump[i-] + pos[i];
sump2[i] = sump2[i-] + pos[i] * pos[i];
}
int m = n - k;
if(m <= )
{
puts("");
continue;
}
double ans = sump2[m] + m * (sump[m] / m) * (sump[m] / m) - 2.0 * (sump[m] / m) * sump[m];
for(int e = m;e <= n;++e)
{
int s = e - m + ;
double eve = (sump[e] - sump[s-]) / m;
double temp = sump2[e] - sump2[s-] + m * eve * eve - 2.0 * eve * (sump[e] - sump[s-]);
ans = min(ans,temp);
}
printf("%.12lf\n",ans);
}
return ;
}