2021牛客暑期多校训练营5 B、Boxes

题目大意

你有 $n$ 个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价 $w_i$ ，你还有一次询问裁判的机会，当然询问裁判代价为 $C$ ，你需要告诉裁判这 $n$ 个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？

Solution

考点：思维

首先我们不询问裁判的话，我们就要把 $n$ 个盒子全部打开，代价为 $\sum\limits_{i=1}^nw_i$

如果我们询问裁判，那么想想我们是不是最多只需要打开 $n-1$ 个盒子，并且如果用 $0$ 代表白球 $1$ 代表黑球如下分析。

考虑开 $0$ 次盒子结束，如果裁判告诉我们有 $n$ 个白球或者 $n$ 个黑球用二进制表示那就是 $0000$ 或 $1111$ 这样的时候结束，那么我们这次代价就只有 $C$ 。

考虑开 $1$ 次盒子结束，那么我们要先开最小花费的那个，并且结束的要求是 $1000$ 或者 $0111$ ，并且还需要对上裁判给你的颜色，所以这里应该概率多乘一个 $\frac{1}{2}$ ，那么这种概率计算为 $\frac{1}{2}^{n-1}$

考虑开 $2$ 次盒子结束，那么我们结束的要求就是 $.100$ 或者 $.011$ ，那么这种概率计算为 $\frac{1}{2}^{n-2}$

以此类推，把开盒子代价排序然后求前缀和处理就行了。

const int N = 1e6 + 7;
int n;
double C;
double p[N];

int solve() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; ++i) p[i] += p[i - 1];

    double res = C;
    for (int i = 1; i < n; ++i)  res += p[i] * pow(0.5, n - i);

    res = min(res, p[n]);
    printf("%.12f\n", res);
    return 1;
}