P8236题解

· · 题解

写在前面

随机随到了这道数学题，于是研究一下（顺便来篇题解）。

部分参考了 paulzrm 大佬的题解，在此致谢。同时，本篇题解也可以作为那篇题解的补充说明（展开了一些详细计算步骤）。

正片

要做一道题，你首先得知道这题让你干什么。

百度可得期望的定义如下：

期望是试验中每次可能结果的概率乘以其结果的总和。

对于本题的情况，直接硬求这个期望得分是不现实的。我们不妨先求出每一堆石头在每轮中被选中的概率和它为得分所做的贡献，单独求和后相乘即可。 小学数学的分配律告诉我们，上面的做法和直接求期望等价。

每堆石头对最终得分做的贡献很好求，就是它的大小，在一开始一个循环扫一遍即可。接下来我们只需要考虑每堆石子被选中概率即可。

想象这样一种场景：现在场上剩 n 堆石子，要选两堆进行合并。对于第一堆有 n 种选法，对于第二堆有 (n - 1) 种选法，考虑重复情况，共有 \dfrac {n \times (n - 1)}{2} 种选法。根据上面的结论，对于特定的一堆，有 (n - 1) 种选法可以选中它。接下来我们可以得出和这一堆有关的概率：

设还剩 n 堆石子的时候每个棋子被选中的期望为 f(n)。

由上面的推论和期望的定义，就可以很轻易地得出每一堆石子可能被选中的期望了（具体内容那篇题解已经写的很好了）：f(n)=\dfrac{2}{n}+f(n - 1)。

这样，一个递推的结构就出来了。让我们开始写代码吧。

代码实现

在本题中有一个很重要的点，也是别的题解多次强调过的：本题卡精度。需要 long double 这件事是毋庸置疑的。

printf 爱好者们可以跳过下一段，直接往下看。

众所周知，用默认状态下的 cout 输出时保留的小数位数往往不如我们所愿。但是在头文件 <iomanip> 中，有一个函数叫 setprecision()，用法示例如下：
cout << fixed << setprecision(10) << ans << endl;
其功能为输出 ans（精确到小数点后 10 位）。

让我们上代码：

Code

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#define MAXN 505
using namespace std;

long double n, a[MAXN];
long double s, f;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s += a[i];
    }

    for (int i = 2; i <= n; i++)
    {
        f += (long double)(2) / (long double)(i);
    }

    cout << fixed << setprecision(10) << s * f << endl;
}

2022-6-10 upd：修改了一处笔误。