【牛客竞赛】Boxes题解

题目大意

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

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

题目链接

思路

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

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

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

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

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

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

$$ans = \sum_{i=0}^{n} sum[i] \cdot 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\left(\sum_{i=0}^{n} sum[i] \cdot \frac{1}{2^{n-i}},\ sum[n]\right)$$

代码

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