Boxes

题目大意

有\(n\)个盒子，每个盒子里装有一个球，它可能是黑色或者白色的概率均为\(1/2\)。现在你可以花费\(C\)的价值来获得剩下的所有盒子中剩余的黑色球数量和白色球数量。还可以花费\(w[i]\)的价值去打开一个盒子。

问： 你知道所有盒子中球的颜色的期望花费是多少。 题目链接

思路

首先我们需要知道我们什么情况下可以知道每个盒子中球的颜色，即剩下没开的盒子数量刚好等于剩下的盒子中某个颜色球的数量

（或者我们可以不询问，直接打开所有的盒子）

比如：还剩下三个盒子，然后我们知道剩下的盒子中黑球的数量有3个。

假如我们还无法确定，那么我们打开盒子的顺序一定是从最便宜的开始打开，且如果我们要询问，那一定是要在刚开始时询问（什么时候询问花费都一样，在最开始询问有最大的可能知道剩下的盒子中球的颜色）。

我们定义\(sum[i]\)为\(w[i]\)从小到大排序后的前缀和，\(p[i]\)表示至少打开第\(i\)​个盒子才知道所有盒子球的颜色的概率。

那么根据数学期望的定义，询问之后再一个一个打开的数学期望就是

​ \[ans = \sum_{i=0}^{n}sum[i]*p[i]\]

接下来我们来分析\(p[i]\)怎么算。注意定义至少打开第\(i\)​个盒子才知道所有盒子球的颜色的概率。也就是说，我们打开第\(i-1\)个盒子的时候，仍然不知道，打开了第\(i\)个盒子的时候，刚好就知道了。说明：

• 从第\(i+1\)到\(n\)个盒子的颜色都相同
• 第\(i\)个盒子与剩下没打开的盒子颜色不同

第二点有些不好想，因为假如第\(i\)个盒子颜色与剩下的相同，那么我们在打开第\(i-1\)个盒子的时候就已经知道剩下盒子的颜色了。

剩下的盒子有\(n-i\)个，\(n-i\)个盒子颜色颜色相同概率为\(1/2^{n-i-1}\)，而又要与第\(i\)个盒子的球颜色不同，所以要再乘以\(1/2\)。

综上\(p[i]=1/2^{n-i}\)​。

还有，假如我们这么得到的期望还不如直接不询问，全部打开的话，那我们完全可以直接全部打开。

所以

​ \[ans=max(\sum_{i=0}^{n}sum[i]*(1/2^{n-i}), sum[n])\]​

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxN = 1e5 + 7;

int n;

double a[maxN], preSum, ans, C;

bool cmp(double x, double y)
{
    return x < y;
}

int main()
{
    cin >> n >> C;
    ans = C;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + n,cmp);
    for(int i = 1; i <= n; ++i) {
        ans += preSum * pow(0.5, n - i + 1);
        preSum += i[a];
    }
    ans = min(ans, preSum);
    printf("%.7f", ans);
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/08/15/Boxes/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！