B.Boxes
题意：
N
N
N个装有黑白球的盒子(每个盒子一定有且只有一个球),你需要知道所有盒子里面都是什么球，为此你需要开盒子，打开第
i
i
i个盒子需要花费
w
i
w_i
wi的代价,同时你可以花费
C
C
C的代价先知道里面有多少个黑球，现在问你最小的期望花费。
题解：
很明显，我们可以有两种策略：
- ①不询问，把所有盒子都开完。
- ②先询问，然后再开盒子，直到开到不用开了为止。
第一种策略很容易算，因为开每个盒子的概率是1，所以期望花费就是 Σ i = 1 n w i Σ^n_{i = 1}w_i Σi=1nwi。
但是第二种策略我们就需要去考虑一个东西，对于当前盒子
i
i
i来说，什么情况下我们可以不用再开这个盒子
i
i
i了。
其实就只有两种情况，要么剩下的盒子里(包括盒子
i
i
i)都是黑球了，或者都是白球了（也就是后缀是都是0或者后缀都是1的情况）。
例如：
如果盒子数是4的话，我们是这样去分析的：
首先我会先去考虑是否需要开第一个盒子，不需要再开第一个盒子的情况就只有两种（0000，1111），也就是
2
/
2
4
2/2^4
2/24，那么我们必须要开第一个盒子的概率就是
1
−
(
2
/
2
4
)
1-(2/2^4)
1−(2/24)。
然后我考虑是否需要开第二个盒子，不需要再开第二个盒子的情况有（0111，1000，0000，1111），也就是
4
/
2
4
4/2^4
4/24，那么必须要开第二个盒子的概率就是
1
−
(
4
/
2
4
)
1-(4/2^4)
1−(4/24)。
同理，我们可以考虑是否开第三个盒子，求出必须要开第三个盒子的概率。
这里需要注意，最后一个盒子是不需要去开的，因为我们询问过总数，所以我们开完前
n
−
1
n -1
n−1个盒子之后，一定可以确定第
n
n
n个盒子里是
0
0
0还是
1
1
1。
也就是说我们只需要确定
1
到
n
−
1
1到n-1
1到n−1每个盒子必须要开的概率就可以。
这里我们设必须要开第 i i i个盒子的概率为 p i p_i pi，那么我们就可以得出 p i = 1 − 1 / ( 2 n − i ) pi = 1 - 1/(2^{n-i}) pi=1−1/(2n−i)，所以我们第二种策略的期望花费就是： C + Σ i = 1 n − 1 w i ∗ ( 1 − 1 / ( 2 n − i ) ) C + Σ^{n-1}_{i = 1}w_i * (1 - 1/(2^{n-i})) C+Σi=1n−1wi∗(1−1/(2n−i))。接着我们就可以想到，因为 p i p_i pi恒定，所以我们需要让 w i w_i wi尽可能的小。
如果我只开一个箱子，那么我一定是开最小价值的箱子，同理，开两个箱子一定是价值最小和价值次小的箱子。所以我们的开箱顺序就应该是从价值最小的箱子开到价值最大的箱子。需要对箱子的价值从小到大排序。
答案就是对两种策略得到的期望花费求一个最小值就行。
一些细节：
因为
n
n
n是
1
e
5
1e5
1e5，而我们需要求
1
−
（
1
/
2
1
e
5
）
1 - （1/2^{1e5}）
1−（1/21e5）, 一般来说可以用快速幂取模求，但是这道题目没有要求取模，我们没办法存下
2
1
e
5
2^{1e5}
21e5这么大的数。但是我们发现我们并不需要求出
2
n
2^n
2n，只需要直到
1
/
2
n
1/2^n
1/2n是多少就可以，可以发现这是一个分子为
1
1
1，且分母很大的分数，题目里给出的精度是
1
e
1e
1e-
6
6
6，这就意味着只要分母大到一定的程度，无论
1
/
2
n
1/2^n
1/2n是多少都没办法影响到我们的答案，我们可以把这个数看成
0
0
0。
我写的时候是只要分母大于了
1
e
10
1e10
1e10，也就是这个数是小数点后
10
10
10位的时候，就不会再影响到答案。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
double w[N];
int main() {
int n;
double C;
double ans1 = 0, ans2 = 0;
scanf("%d%lf", &n, &C);
for(int i = 1; i <= n; ++ i) {
scanf("%lf", &w[i]);
ans1 += w[i];
}
ans2 += C;
long long res = 2;
sort(w + 1, w + 1 + n);
for(int i = 1; i <= n - 1; ++ i) {
double p;
if(res >= 1e10) p = 0;
else p = 1.0/res;
ans2 += w[n - i] * (1.0 - p);
if(p != 0) res *= 2;
}
printf("%.6f\n", min(ans1, ans2));
}