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;

}

巴特西

2014 Asia AnShan Regional Contest --- HDU 5073 Galaxy

Galaxy

Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5073

最新文章

热门文章