B Boxes

https://ac.nowcoder.com/acm/contest/11256/B

思路：只要使用一次hints，以后的每一步都可以知道剩下多少个黑球，所以最少花费有两种情况。

一、全部盒子开一遍

二、先用一次hints，再从小到大开盒子。注意到，每开一个盒子都有一定概率直接结束（后面全都是白球或全都是黑球）

那就借样例2来模拟一下期望

  
     
前缀和分别是      

一.先排个序，再预处理出前缀和数组， 即为第一种情况

二.1.先花费

2.思考一下，一个盒子都不开的时候结束的概率是什么 全部小球同色 (黑 白) ，但是这个时候的前缀和为 ，就不用管

3.然后就要注意了，因为我们已经知道后面的黑球数量，换句话说，后面必定要全黑或全白（这个或和上面的 不太一样）才能结束这不是废话吗，不是，因为此时的概率不用再乘 了！假设我们摸完了第 个球，第 个球的颜色还不清楚，则此时结束的概率为

4.所以

因此

code

https://pastebin.ubuntu.com/p/STwV7cQZgw/

这次应该没啥问题了吧