原题链接
https://ac.nowcoder.com/acm/contest/11256/B
题目大意
有 n n n个盒子,每个盒子内有一个白色或黑色的球,概率都是 1 2 \frac{1}{2} 21,不同盒子中的球的颜色相互独立。现在需要猜测每个盒子内球的颜色。有以下两种方法帮助猜测:
1.花费
w
i
w_i
wi,打开第
i
i
i个盒子直接观察其中球的颜色;
2.花费
C
C
C,询问剩余未打开的盒子中黑球的数量;
求确定所有颜色的最小花费的数学期望。
题解
首先,如果我们花费 C C C得知了未打开的盒子中有多少个黑球,并且可以通过开盒子算出接下来还有多少黑球,所以我们只需在最初进行这部操作即可。
接下来,计算每一步的期望值。考虑当剩余的所有球都为同一种颜色时,不继续开盒子,而剩余盒子都为同一颜色的概率为 1 2 n − i \frac{1}{2^{n-i}} 2n−i1,所以当前步的期望值为 w i × ( 1 − 1 2 n − i ) ( 1 ≤ i ≤ n ) w_i\times (1-\frac{1}{2^{n-i}})(1\leq i\leq n) wi×(1−2n−i1)(1≤i≤n)
所以可得出总期望值为:
C
+
∑
i
=
1
n
w
i
×
(
1
−
1
2
n
−
i
)
C+\sum^{n}_{i=1}w_i\times (1-\frac{1}{2^{n-i}})
C+i=1∑nwi×(1−2n−i1)
同时,如果直接将所有盒子打开的总花费更优时,总期望值为 ∑ i = 1 n w i \sum\limits^{n}_{i=1}w_i i=1∑nwi,此时我们只需计算直接 全部打开的总花费 并与通过得知剩余黑球数量算得的期望值 进行比较即可。
注意:要将 w w w数组进行从小到大的排序,才能确保每一步的操作为当前最优。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
double v[N],C,ans,e=1,m=0;
int main()
{
scanf("%d%lf",&n,&C);
for(int i=1;i<=n;i++)
{
scanf("%lf",&v[i]);
m+=v[i];
}
sort(v+1,v+n+1);
ans=C;
for(int i=n;i>0;i--)
{
ans=ans+v[i]*(1-e);
e/=2.0;
}
printf("%.8lf",min(ans,m));
}