bzoj2048 书堆
有n本厚度不计的完全相同的书，长度均为m。
问在能放稳的情况下，最上面一本书伸出桌面最长的长度是多少?
显然重心刚好在桌子边缘最优。
令fn表示n本书时最长伸出桌面的长度，则有fn=∑i(i>0&&i<=n) m/(2*i)
n较小的时候直接暴力计算
n较大的时候用1+1/2+1/3+...+1/n=ln(n+1)+r,r=0.5772156649
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <math.h>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;long long n,m;int main(){ scanf("%lld%lld",&n,&m); double ans=0; if(n>10000){ ans=(log(1.+n)+0.57721566490153286060651209)*m/2.; } else{ for(int i=1;i<=n;++i)ans+=1.*m/i/2.; } printf("%d\n",int(ans-1e-10)); return 0;} |
