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

题目大意

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

Solution

考点：思维

首先我们不询问裁判的话，我们就要把个盒子全部打开，代价为

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

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

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

考虑开次盒子结束，那么我们结束的要求就是或者，那么这种概率计算为

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

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