P16639 [GKS 2018 #A] Lucky Dip

你正在参加“盛大 Kickstart 幸运抽奖”活动，奖品非常精彩且令人惊叹（也有些不太好的奖品）！ 在这个幸运抽奖中，有一个装有 $N$ 个物品的袋子。袋子中的第 $i$ 个物品的价值为 $V_i$。你将把手伸进袋子，随机抽取一个物品；袋子中的所有物品被抽中的概率相等。组织者希望让参赛者感到自己有一定的选择权，因此在你抽出一个物品后，你可以选择保留它，或者将其放回袋子并重新抽取（即“重抽”）。注意，放回的物品与袋子中其他物品被抽中的概率相同。你最多只能重抽 $K$ 次。如果你使用了 $K$ 次重抽，则必须保留第 $(K+1)$ 次抽到的物品。 如果你以最优策略进行游戏，以最大化最终持有的物品价值，那么该物品的期望价值是多少？

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。 每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $K$：袋子中的物品数量，以及最多可以重抽的次数。第二行包含 $N$ 个整数 $V_i$，表示第 $i$ 个物品的价值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述期望价值。如果答案与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

在样例 #1 中，你不能重抽，所以期望价值就是袋子中物品的平均值，即 $(1 + 2 + 3 + 4) / 4 = 2.5$。 在样例 #2 中，最佳策略是：如果抽到价值为 $10$ 的物品就保留，否则重抽。第一次或第二次抽到该物品的概率为 $1 - (2/3)^2 = 5/9$，因此期望价值为 $(5/9 \times 10) + (4/9 \times 1) = 6$。 在样例 #3 中，由于所有物品价值相同，重抽多少次都没有影响，因此期望价值为 $80000$。 注意，样例 #3 和 #5 不会出现在小数据集中。 ### 限制条件 $1 \le T \le 100$。 $1 \le V_i \le 10^9$。 $1 \le N \le 2 \times 10^4$。 **小数据集（测试集 1 – 可见）** $0 \le K \le 1$。 **大数据集（测试集 2 – 隐藏）** $0 \le K \le 5 \times 10^4$。 翻译由 DeepSeek V4 Pro 完成