B:Boxes

题目链接：https://ac.nowcoder.com/acm/contest/11256/B

题意：

有nn个盒子，每个盒子中要么是黑球，要么是白球。在盒子未打开之前不知道盒子内球的颜色，打开盒子需要花费wiw_i。求出得知所有盒子中球是什么颜色所花费的期望。你可以选择花费价值cc来获得一个提示，告诉你剩下的未打开的盒子中有多少个黑球。

思路：

提示只需要获取一次即可。因为在最开始时获取提示后可以全局有效。

第一种打开方式为将权值排序后，从小到大计算能取到当前位置的概率。能取到第ii个位置说明取了第i−1i-1个位置上的还不是一个确定局面。确定局面为后面的一段全为同色。所以i−ni-n肯定不为同色。同色的情况有两种，全为黑色或者全为白色。则第ii个位置上能取的概率为1−22n−i+11-\cfrac{2}{ 2^{n-i+1} }，即p(i)=1−12n−ip(i)=1-\cfrac{1}{ 2^{n-i} }。期望E=∑i=1np(i)∗w(i)E=\displaystyle\sum_{i=1}^np(i)*w(i)。

第二种打开方式为全部打开。二者取最小值即为答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 1e5 + 9;
double a[N];
int n;
double p(int x) {
    return (double) ( 1.0 - (1.0 / (pow(2,n-x))));
}

int main() {
    double k;
    cin >> n >> k;
    double ans = 0;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], ans += a[i];
    double res = 0;
    sort(a+1,a+1+n);
    for (int i = 1; i <= n; i ++ ) {
        res += (double)a[i]*1.0*p(i);
    }
    printf("%.8lf\n",min(res + k,ans));
}