[数据结构与算法]Boxes（牛客暑假第五场）

Boxes
链接: link.
题目：



题意：
有$n$个盒子在你面前。你知道每个盒子都装着白色或黑色的球。每个盒子中为黑（白）色球的概率为二分之一。打开每个盒子都需要对应所需代价 ，打开一个盒子后，你可以看到这个盒子里面的球。当然，除了打开所有盒子，你没有办法知道所有的颜色。但当你支付$c$后，你可以知道尚未打开的所有盒子中的黑球数量。计算出所有颜色的球的最低成本的数学期望是什么？
题解：
感觉还是需要理解一下，当时看题就完全没有什么头绪。
第一种方法，一个一个拆开；
第二种，先支付$c$,可以知道总共有多少个黑球，注意需要将数组排序才能得到此时最优情况，计算每一步的期望值，假设后面的球均为同一个颜色即不用再开盒子，同色概率为$\frac{1}{2^{n?i}}$，则此时的期望值为$a[i]?(1?\frac{1}{2^{n?i}})$.所以此种情况下的总期望值为$c+{\sum }_{i=1}^n{a}_i\frac{1}{2^{n?i}}$.
最后比较找最小即可。

#include<bits/stdc++.h>
using namespace std;
double a[100010];
int main()
{
	int n;
	double c;
	cin>>n>>c;
	double ans1=0,ans2=0,p=1.0,ans;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans1+=a[i];
	}
	sort(a+1,a+1+n);
	ans2=c;
	for(int i=n;i>=1;i--)
	{
		double x=1-p;
		ans2+=a[i]*x;
		p=p*0.5;
	}
	ans=min(ans1,ans2);
	printf("%.6lf\n",ans);
	return 0;
}