牛客多校4.B.Boxes 概率

牛客多校4.B.Boxes

Problem Analysis

给定 n n n​个盒子在你前面，等概率的装着白球或者黑球，且各自独立。现在你来猜盒子里的球的颜色，你可以打开盒子，但是需要花费盒子对应的权值。额外的，会提供给你所有没开盒子里剩余多少黑球，但是也要花费一个权值 C C C，那么问：确定盒子里所有球颜色需要花费最小权值的期望。

首先需要确定， C C C​要花则仅能花费一次，那么开盒子方案分为：

1. 直接全开， a n s 1 = ∑ W i ans_1 = \sum W_i ans1​=∑Wi​​
2. 将权值升序排列，花费 C C C​​​后逐个开盒子，开出所有黑球后即终止。 a n s 2 = C + ∑ W i ∗ ( 1 − 1 2 n − i ) ans_2 = C+\sum W_i*(1- \frac{1}{2^{n - i}}) ans2​=C+∑Wi​∗(1−2n−i1​)​

两者取最小值即可。

AC Code

#include 
#define int long long
#define mod 1000000007
#define N 1000005
using namespace std;

long double c, ans1, ans2, base = 0.5;
double a[100005];
signed main(){
    int n = 0; cin >> n >> ans2;
    for (int i = 1; i > a[i];
        ans1 += a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = n - 1; i; i--){
        ans2 += (1 - base) * a[i];
        base *= 0.5;
    }
    cout