题目描述

跳蚤国有 $n$ 个城市，编号 $1$ 到 $n$，国王住在 $1$ 号城市。
每个城市有一个相同规格的圆柱形水箱，初始水位 $h_i$ 互不相同。

操作规则：每次可以选择任意多个城市，将它们的水箱连通足够长时间后关闭，这些城市的水位会变成它们的算术平均值。

限制：最多进行 $k$ 次操作。

目标：最大化 $1$ 号城市的最终水位。

---

题意分析

1. 操作的本质

• 连通操作相当于水量重新分配：选中的城市总水量不变，但平均分配到每个选中城市
• 这是可逆操作吗？不是，因为水位会永久改变
• 操作可以任意选择城市集合，不要求相邻或连续

2. 关键约束

• 初始水位各不相同
• 操作次数 $k$ 有限
• 最终只关心 $1$ 号城市的水位

3. 问题转化

我们需要设计一个操作序列，使得经过至多 $k$ 次操作后，$1$ 号城市的水位尽可能高。

---

思路推导

第一步：基本观察

观察1：如果只进行 $1$ 次操作，最优策略是让 $1$ 号城市与所有水位高于它的城市连通。
证明：设 $S$ 是水位高于 $h_1$ 的城市集合，连通后 $1$ 号城市水位为 $\frac{h_1 + \sum_{i \in S} h_i}{|S| + 1}$，这显然优于任何不包含所有高水位城市的方案。

观察2：操作顺序很重要。如果先让 $1$ 号城市与较低水位城市连通，会降低后续与高水位城市连通的效果。

第二步：多操作情况分析

考虑 $k \geq 2$ 的情况：

策略：应该让 $1$ 号城市的水位单调递增。

• 第一次操作：$1$ 号城市与某个高水位城市连通
• 第二次操作：$1$ 号城市（现在水位已提高）与另一个更高水位城市连通
• 依此类推...

关键结论：最优策略是让 $1$ 号城市按水位从低到高的顺序依次与其他城市连通。

第三步：数学模型

将城市按水位从低到高排序：$a_1 \leq a_2 \leq \cdots \leq a_n$
设 $1$ 号城市在排序后的位置为 $p$（即 $a_p = h_1$）。

我们最终要让 $1$ 号城市与某个区间 $[l, r]$ 的城市连通，其中 $l \leq p \leq r$。

动态规划状态设计： 设 $dp[i][j]$ 表示考虑前 $i$ 个城市（排序后），使用 $j$ 次操作时，$1$ 号城市能达到的最大水位。

状态转移： 对于每个 $i \geq p$，考虑最后一次操作连通了区间 $[l, i]$：

$$dp[i][j] = \max_{p \leq l \leq i} \left\{ \frac{\sum_{t=l}^i a_t + (l-p) \cdot dp[l-1][j-1]}{i-p+1} \right\} $$

解释：

• $\sum_{t=l}^i a_t$：区间 $[l,i]$ 城市的水位和
• $(l-p) \cdot dp[l-1][j-1]$：区间 $[p,l-1]$ 城市在之前操作中已经达到的水位和
• 分母 $i-p+1$：从 $p$ 到 $i$ 总共 $i-p+1$ 个城市

第四步：斜率优化

直接计算上述转移是 $O(n^2k)$，需要优化。

令 $sum[i] = \sum_{t=1}^i a_t$，转移方程重写为：

$$dp[i][j] = \max_{p \leq l \leq i} \left\{ \frac{sum[i] - sum[l-1] + (l-p) \cdot dp[l-1][j-1]}{i-p+1} \right\} $$

令 $F(l) = sum[l] - l \cdot dp[l][j-1]$，经过变形可以得到斜率优化的形式。

维护一个下凸包，在凸包上二分查找最优的 $l$，将复杂度降为 $O(nk)$。

第五步：实现细节

1. k的限制：实际上 $k$ 不需要很大，因为最多 $n-1$ 次操作就能让所有城市水位相同

   k = min(k, n);
   K = min(k, 14);  // 实践中14次操作已经足够接近最优
   

2. 精度处理：使用高精度 Decimal 类确保计算精度

3. 剩余操作处理：如果完成主要操作后还有剩余次数，贪心地与剩余的最高水位城市平均

---

算法流程

1. 输入：$n, k, p$ 和 $h$ 数组
2. 预处理：
   • 将城市按水位排序
   • 找到 $1$ 号城市的位置 $p$
   • 计算前缀和 $sum$
3. 动态规划：
   • 初始化 $dp[i][0] = h_1$（$i \geq p$）
   • 对于 $j = 1$ 到 $K$：
     • 使用单调队列维护凸包
     • 计算 $dp[i][j]$ 的所有状态
4. 处理剩余操作：
   • 对于 $k-K$ 次剩余操作，贪心地与未处理的高水位城市平均
5. 输出：保留足够精度的小数结果

---

复杂度分析

• 时间复杂度：$O(n \log n + nK)$，其中 $K = \min(k, 14)$
• 空间复杂度：$O(n)$，使用滚动数组

---

总结

本题通过动态规划建模，利用斜率优化高效求解，结合贪心思想处理剩余操作，最终使用高精度计算确保答案正确。关键在于理解操作顺序对结果的影响，以及如何通过数学变形应用斜率优化技巧。