BitComet 旗下网站

转到日志
相关贴吧:
acm of zju

zju2766 Local Maxima

楼主 发表于:2008-08-04 23:16:32 [回复]

/*Local Maxima
2008-08-04 23:04:28 Accepted 2766 C++ 00:00.10 4752K 天将降大任于我
电脑上内存不够大,运行不了,开double stack[500000]需要占用4G的内存,但是看了大牛的A了

  有大牛如是解说:
  输入:1 2  输出:1.00000000  1.50000000
  例如n=2:a、b(a>b))两个数的排列可能是a、b或b、a,则答案为(2+1)/2=1.5;以次类推,题目变为求1/1+1/2+1/3…+1/n的值。
由于数值太大(2^31-1),所以考虑用一积分形式(将曲线1/k积分)代替直接求解,以避免超时,
stack[]中保存的是k从1到500001时的答案,这一部分可以直接求解。接下来就要用到积分,主要是
考虑数值精确度的问题。当k足够大时,曲线1/k近似曲线,500000以前直接求,500000之后用
cur=log((double)i+0.5)-log(500000.5)+stack[500000]来计算。

 

log(x)即为函数ln(x)

*/
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
       long n; double s=0;double stack[500004];
       for(int i=1;i<=500001;i++)
    {  s+=1/(double)i;
          stack[i]=s;
    }
       while(scanf("%ld",&n)!=EOF)
    {
     if(n>500001) s=log((double)n+0.5)-log(500000.5)+stack[500000];
     else s=stack[n];
     printf("%.8lf\n",s);
    }
    return 0;
}


心难泰,世风坏,旧时正气今何在?正义寡,人情薄,闻道虽多,茅塞不开。怪!怪!怪! 空等待,几多载,冲出重围人心快!暴雨打,狂风袭,任他折磨,此志难改。耐!耐!耐!

1楼 发表于:2008-08-04 23:58:33 [回复]


学而时习之,不亦说乎?有朋自远方来,不亦乐乎?人不知而不愠,不亦君子乎?

 

您现在还没有登录,请在登录后发贴