问题描述
蚂蚁是勤劳的动物，他们喜欢挑战极限?现在他们迎来了一个难题！蚂蚁居住在图书馆里，图书馆里有大量的书籍。书是形状大小质量都一样的矩形。蚂蚁要把这些书摆在水平桌子的边緣。蚂蚁喜欢整洁的布置，所以蚂蚁规定书本必须水平摆放，宽必须平行于桌緣（如图），而且不允许同一高度摆多本书。
https://cdn.luogu.org/upload/pic/30575.png
蚂蚁想要让书本伸出桌子边缘尽量远，同时不让书因为重力垮下来。它们己经用不知道什么方法测出了书的长度M(如图)。如果总共有N本书，请你帮忙计算如何摆放使得最多水平伸出桌缘多远。你不用考虑蚂蚁用什么方法搭建这堆书。
如果某本书以上的所有书的重心的竖直射影不在这本书上，或者正好落在在这本书的边界上，那么这堆书是不稳定的，会因为重力而垮下来。
考虑以下的假设：
- 不考虑地球自转，重力系数也不因高度改变；
- 书是质量均匀，质地坚硬的理想二维物体；
- 在不会垮的前提下，每本书的位置坐标可以是任意实数。
输入格式
第一行正整数 N M
输出格式
一行(有换行符),L,表示水平延伸最远的整数距离 (不大于答案的最大整数)
样例输入输出
输入输出样例 1
Input Output
1 100 49
输入输出样例 2
Input Output
2 100 74
解析
一道物理题加数学题......
首先，通过杠杆原理可以得到，最后的长度为
[ans=frac{m}{2}*sum_{i=1}^{n}{frac{1}{2i}}
]
对于(sum)中的部分，将(1/2)提出来后就是调和级数，但直接计算不仅时间不够，而且精度也不够。我们可以通过数学证明百度百科发现，第n个调和数与n的自然对数之差收敛于欧拉常数，即第n个调和数可以近似地估计为
[sum_{i=1}^{n}{frac{1}{i}}=ln(n)- gamma
]
其中(gamma =0.5772156649......)。
所以，对于n<1e7，我们直接计算；对于n>1e7，我们用近似公式计算。注意题目说重心不能落在边缘，所以要减去一个极小值后向下取整后输出答案。
代码
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-9;
long long n,m,i,ans;
double ret;
int main()
{
cin>>n>>m;
if(n>10000000) ret=(log(n)+0.5772156649)/2;
else{
for(i=1;i<=n;i++) ret+=1.0/(2.0*i);
}
ans=m*ret-eps;
cout<<ans<<endl;
return 0;
}