uva10883_Supermean

题目大意：给出n个数，每相邻两个数求平均数，得到n-1个数，再求平均数，得到n-2个数，......一直到最后一个数，输出这个数。

题目很简单，就是中间数据会比较大有点复杂，超过double的范围，而结果又比较小，这时候可以考虑只存储中间数据的log值，改乘除运算为对数的加减运算，然后对结果求幂即可，需要注意的一点是负数不能取对数，先提取负号。

很容易得到：ans=sum(C(n-1,i)*a[i])/(2^(n-1)) , i=0~n-1;

提前将c(n-1,i)的值求出，log_C存储对数:log_C[i]=log_C[i-1]+log10(n-i)-log10(i);

由于无法将log(sum(C(n-1,i)*a[i]))分解，可以求出每个log(C(n-1,i)*a[i]/(2^(n-1)))再求和。

for (int i=0;i<n;++i)
　　if (a[i]<0)
　　　　ans-=pow(10,log_C[i]+log10(-a[i])-log10(2)*(n-1));
　　else
　　　　ans+=pow(10,log_C[i]+log10(a[i])-log10(2)*(n-1));

代码如下：

/*************************************************************************

    > File Name: 10883.cpp

    > Author: Chierush

    > Mail: qinxiaojie1@gmail.com

    > Created Time: 2013年06月18日 星期二 23时50分42秒

 ************************************************************************/

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <set>

#include <cstdio>

#include <string>

#include <vector>

#include <map>

#include <cmath>

#include <algorithm>

#define LL long long

#define LLU unsigned long long

using namespace std;

double log_C[50005],a[50005];

int main()

{

    int n,T;

    scanf("%d",&T);

    for (int kcase=1;kcase<=T;++kcase)

    {

        scanf("%d",&n);

        for (int i=0;i<n;++i)

            scanf("%lf",&a[i]);

        log_C[0]=log10(1);

        for (int i=1;i<n;++i)

            log_C[i]=log_C[i-1]+log10(n-i)-log10(i);//,printf("%lf %lf\n",log_C[i],pow(10,log_C[i]));

        double ans=0.0;

        for (int i=0;i<n;++i)

            if (a[i]<0)

                ans-=pow(10,log_C[i]+log10(-a[i])-log10(2)*(n-1));

            else

                ans+=pow(10,log_C[i]+log10(a[i])-log10(2)*(n-1));

        printf("Case #%d: %.3lf\n",kcase,ans);

    }

    return 0;

}

巴特西

uva10883_Supermean_数学

最新文章

热门文章