题目大意

有 $N$ 个对手，必须用恰好 $K$ 轮比赛全部战胜。
每轮你可以选择若干对手（至少一个）进行比赛，并将他们全部淘汰。
该轮获得的奖金为 淘汰人数 ÷ 该轮开始前剩余总人数。
每轮奖金池固定为 $1$ 元，求最大可能获得的总奖金。

---

问题形式化

设第 $i$ 轮开始前剩余人数为 $s_i$（$s_1 = N$，$s_{K+1} = 0$），该轮淘汰人数为 $d_i = s_i - s_{i+1} \ge 1$，则该轮奖金为：

[ \frac{d_i}{s_i} ]

总奖金为：

[ S = \sum_{i=1}^K \frac{d_i}{s_i} ]

约束条件：

• $d_i \ge 1$
• $\sum_{i=1}^K d_i = N$
• $s_i = N - \sum_{j=1}^{i-1} d_j$

---

初步分析与贪心直觉

我们希望最大化 $\sum_{i=1}^K \frac{d_i}{s_i}$。
由于早期 $s_i$ 较大，此时淘汰更多人（$d_i$ 大）带来的“奖金率”更高，因为分母大而分子增加的比例收益大。
反之，后期 $s_i$ 较小，即使淘汰所有人（$d_i = s_i$）也只能得到 $1$，所以后期收益有限。

因此，最优策略倾向于在前几轮淘汰尽可能多的人，但必须保证后面每轮至少能淘汰 $1$ 人。

---

建立模型与连续近似

为了便于分析，暂时忽略 $d_i$ 为整数的限制，假设可以淘汰任意实数人数。
令 $x_i = \frac{s_{i+1}}{s_i}$（$0 \le x_i < 1$），则：

[ \frac{d_i}{s_i} = 1 - x_i ] [ s_{K+1} = N \cdot \prod_{i=1}^K x_i = 0 \quad \Rightarrow \quad x_K = 0 ]

总奖金变为：

[ S = \sum_{i=1}^K (1 - x_i) = K - \sum_{i=1}^K x_i ]

问题转化为在约束 $x_K = 0$ 和 $N \cdot \prod_{i=1}^{K-1} x_i \ge 1$（因为 $s_K \ge 1$）下，最小化 $\sum_{i=1}^{K-1} x_i$。

---

连续最优解

由均值不等式，当 $x_1 = x_2 = \dots = x_{K-1} = N^{-1/(K-1)}$ 时，$\sum x_i$ 最小。
此时：

[ S_{\text{max}} \approx (K-1)\left(1 - N^{-1/(K-1)}\right) + 1 ]

直观理解：在最优策略下，除最后一轮外，每轮结束后剩余人数按固定比例减少，这个比例是 $N^{-1/(K-1)}$。

---

整数情况与动态规划

实际 $d_i$ 是整数，需要用动态规划精确求解。

状态设计

设 $dp[t][n]$ 表示用 $t$ 轮战胜 $n$ 个人能获得的最大奖金。

转移方程

第 $t$ 轮开始时剩余 $n$ 人，我们选择淘汰 $m$ 人（$1 \le m \le n - (t-1)$，因为后面 $t-1$ 轮至少需要 $t-1$ 人），则：

[ dp[t][n] = \max_{1 \le m \le n - (t-1)} \left( \frac{m}{n} + dp[t-1][n-m] \right) ]

初始条件：

• $dp[0][0] = 0$
• $dp[0][n>0] = -\infty$（不可行）

最终答案：$dp[K][N]$。

---

优化转移

直接转移复杂度 $O(K N^2)$，需要优化。

改写转移：

[ dp[t][n] = \max_{1 \le m \le n - (t-1)} \left( dp[t-1][n-m] - \frac{n-m}{n} \right) + 1 ]

令 $k = n-m$，则 $k$ 的范围是 $[t-1, n-1]$，且：

[ dp[t][n] = 1 + \max_{k = t-1}^{n-1} \left( dp[t-1][k] - \frac{k}{n} \right) ]

对于固定的 $t$，考虑函数 $g(k) = dp[t-1][k]$。
我们要对每个 $n$ 最大化 $g(k) - \frac{k}{n}$，即最大化 $g(k) - \lambda k$ 的形式，其中 $\lambda = 1/n$。

---

凸包技巧（斜率优化）

如果点集 $(k, g(k))$ 构成上凸包（即 $g(k)$ 是关于 $k$ 的凹函数），则可以在凸包上二分查找斜率 $1/n$ 对应的切点，从而在 $O(\log N)$ 时间内找到最优 $k$。

事实证明 $g(k)$ 确实是凹的，因此可以这样优化。
对每个 $t$，维护一个凸包，枚举 $n$ 时在凸包上二分，总复杂度 $O(KN\log N)$。

---

另一种高效方法：WQS 二分

如果去掉“恰好 $K$ 轮”的限制，问题变为：在总淘汰 $N$ 人的前提下，自由选择轮数，最大化总奖金。
这个无限制问题更容易贪心求解：每次选择淘汰人数使 $\frac{d}{s}$ 最大，直到所有人淘汰完。

WQS 二分的思想是：给每轮增加一个惩罚 $\lambda$，然后求解无限制问题，通过调整 $\lambda$ 使得最优解恰好使用 $K$ 轮。

具体步骤：

1. 二分惩罚 $\lambda$。
2. 对于给定的 $\lambda$，用贪心计算最大收益 $f(\lambda)$ 和轮数 $cnt(\lambda)$。
   • 贪心规则：当剩余 $s$ 人时，选择淘汰 $d$ 人最大化 $\frac{d}{s} - \lambda$，直到所有人淘汰。
3. 找到 $\lambda$ 使 $cnt(\lambda) = K$。
4. 最终答案 $= f(\lambda) + K\lambda$。

该方法复杂度 $O(N \log C)$，其中 $C$ 是二分精度范围，效率更高。

---

总结

1. 贪心本质：优先在前几轮淘汰更多人。
2. 连续近似解：$S_{\max} \approx (K-1)\left(1 - N^{-1/(K-1)}\right) + 1$。
3. 精确解法：
   • DP + 凸包优化：$O(KN\log N)$
   • WQS 二分 + 贪心：$O(N \log C)$（推荐）
4. 注意输出精度要求 $10^{-8}$，需用 long double 计算。

---

本题结合了贪心策略、动态规划优化和凸函数性质，是一道经典的优化问题。