2021 Niuke multi school training camp 5 (question b)

B：Boxes

The question ：

Yes n Boxes , Each box will have a ball , The color of the ball is black or white , The probability of each color is 1/2, The only way to see the ball in the box is to open the box , Open the first i The cost of a box is wi, You can also ask God once , God will tell you how many black balls there are in the remaining box , The cost of asking is C, Ask what is the minimum expected value of the cost of determining the color of the ball in all boxes

analysis ：

There are two situations , One is to ask God , One is not asking God , If you don't ask God, it must be n All boxes are open , The answer is sum[n], Represents the former n Sum of weights , If you ask God, there is n In this case , The answer of God is different , this n The states of the boxes are 2^n Kind of , First, sort according to the unpacking weight from small to large , Then unpack in this order , If you drive to a position, you already know that the boxes behind are all 1 Or all 0 After that, it means success , We can write it as n = 3 The results are as follows ：
3 Box status The weight of unpacking and
0 0 0 0
0 0 1 w1+w2
0 1 0 w1+w2
0 1 1 w1
1 0 0 w1
1 0 1 w1+w2
1 1 0 w1+w2
1 1 1 0
Just look at the position of the dividing line , Altogether i A place , The first i The weight of each position should be added 2^i Times (sum[i]), The probability of each case is
1/2^n, So the answer adds up to
Finally, don't forget to take a minimum value without asking God . Now let's look at the code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+10;
double w[N];
double sum[N];
int main()
{
    
	int n;
	double c;
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		scanf("%lf",&w[i]);
	sort(w+1,w+n+1);// Sort the costs from small to large  
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+w[i];
	double ans=c;
	double t=0.5;
	for(int i=n-1;i>=1;i--)
		ans+=t*sum[i],t/=2;
	if(ans>sum[n]) ans=sum[n];
	printf("%.10lf",ans);
	return 0;
}