牛客多校赛题解（五）

1.Boxes

题目链接:B-Boxes_2021牛客暑期多校训练营5 (nowcoder.com)

题目大意

有一个卡池，卡池里有n个盒子，打开每个盒子都需要ai块钱，每个盒子里面有白色与黑色两种球，抽到任意一种颜色的概率都是0.5，现在有一个内鬼，他知道卡池里面有多少的黑球，但是你得用C块钱去贿赂他，现在问，如果你想要知道卡池里总共有多少球，最少需要花费的期望是多少

解题思路

有两种情况：

1. 当内鬼太贪心，情报费加上拆盒费用已经大于我拆开所有的盒子的花费总额，这时的期望就是我直接拆开所有的盒子
2. 当内鬼比较良心，这时候我们只需要问一次内鬼就行，然后开始拆盒子。

求期望：

1. 开盒子需要一直开到后面的所有球颜色相同（都为黑色或者都为白色）
2. 每种情况的花费就是开盒子的那些花费

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-05 22:07:22
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int M = 1e9 + 10;

double a[N];

int main()
{
    int n;
    double c, tot = 0, e = 0;

    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        tot += a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; i++)
    {
        a[i] = a[i - 1] + a[i];
        // cout << a[i] * pow(0.5, n - i) << " ";
        e += (a[i] * pow(0.5, n - i));
    }
    // cout << endl;
    // cout << e + c << endl;
    printf("%.12lf\n", min(e + c, tot));
    return 0;
}