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
#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; }