题解 P4820 【[国家集训队]书堆】

· · 题解

这题....
一道极好的初中物理+(貌似是高中?)数学题。

通过初中物理的学习,我们知道了杠杆平衡。

通过打表/手算找规律,发现答案 = (1 / 2 + 1 / 4 + .. 1 / (2n)) * m.

貌似是调和级数H(n) / 2???

ok,精度爆炸qwq.

好了，我们baidu一下,发现有个公式: (ln(n) + 0.5772156649) / 2.

怎么还是WA？？？

回顾下题面：

“如果某本书以上的所有书的重心的竖直射影不在这本书上，或者正好落在在这本书的边界上，那么这堆书是不稳定的，会因为重力而垮下来。”

所以。。。 我们的答案不能正好取到,还要减去一个重心的位移。。。

减去一个很小的实数(不影响精度)即可。

代码：


#include <bits/stdc++.h>
#define LL long long
#define db double
using namespace std;
inline LL read(){
    LL x = 0,f = 1; char c = getchar();
    while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
    while (c != EOF && isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}
inline void write(LL x){
    int k = 0;char put[40];
    if (!x) putchar('0');
    if (x < 0) putchar('-'),x = -x;
    while (x)  put[++k] = (x % 10) + '0',x /= 10;
    while (k)  putchar(put[k]),--k;
    putchar('\n');
}

LL n,m,ans;
db f = 0,eps = 1e-6;

int main(){
    n = read(),m = read();
    if (n >= 1e7) f = (log(n) + 0.5772156649 )/ 2;
    else for (int i = 2; i <= n*2; ++i,++i ) f += 1.0 / i;
    ///小数据一定要暴力！上面只是个近似公式!!!!
    ans = m * f - eps;
    write(ans);
    return 0;
}