题意
有一个长度为 n 的数组 H（元素互不相同），你可以进行 m 次操作，每次取若干元素，把他们都赋值为他们的平均值。求 $H_1$ 最终最大能达到多少，要求计算过程中保留到小数点后 p 位。
简单观察
贪心一下，大概就能感受出来最优解的搞法：
- 将 $H_{[2,n]}$ 排序，选一个后缀，并划分为 m 个区间。
- 把 $H_1$ 从小到大依次和这些区间内的数联通。
这个感觉是对的，但是严格证明需要以下结论：
- 小于等于 $H_1$ 的数没用（显然）
- 假如每次操作都包含 $H_1$，每个数不会选两次（操作过之后就小于等于 $H_1$ 了）
- 存在一个最优方案，每次操作都包含 $H_1$
（借鉴 @lim 的证法）：
考虑最优方案中，最后一次不包含 $H_1$ 的操作，不妨设操作的集合为 S，会发现：S 中的数，之后最多会再被操作一次（之后的操作都包含 $H_1$，由上一个引理可得）。
可以发现，假如不进行这次操作，并把 S 中之后还被操作过的数，从小到大排序之后，替换到上述方案中的位置里，可以得到不劣的答案。
- 相邻两次操作，所选的（除了 $H_1$ 之外的）数，值域不相交（如有相交，改成不相交更优）
- 相邻两次操作，先进行所选的（除了 $H_1$ 之外的）数，较小的操作。（否则交换更优）
- 将 $H_{[2,n]}$ 排序，每次操作都是一个区间（如果选的数不连续，可以把第一个数到最后一个数中间所有数都选了（由上上个引理，这些数不可能被别的操作用过），不劣）
- $m\ge n$ 的情况与 $m=n-1$ 相同
暴力做法
把小于 $H_1$ 的东西扔掉，将 H 从小到大排序，记 sH 为 H 的前缀和。
$dp(i,j)$ 表示搞完前 i 次操作，并规定 j 之前的东西都不能再操作了，此时 $H_1$ 的最大值。转移显然：
$$ dp(i,j)=\max_{k转移优化
仔细观察转移方程，感觉和一般的斜率优化不太一样，倒是有点 0/1 分数规划的感觉。因此，我们可以考虑二分一个 x，看看需要满足什么条件：
$$ \begin{aligned} \max_{k
并且我们发现，这些一次函数虽然截距是小数，但是斜率是整数。因此我们可以轻松算出两个函数的交点，不需要高精度除高精度。
带 log 做法
于是现在我们可以用一个 queue 维护凸包（斜率是单调增的），然后每次查询，二分出凸包和直线的交点在凸包的哪一段上。复杂度 $O(n^2 p\log n)$，并没有太多分。
去掉 log
显然，$dp(i,j)>dp(i,j-1)$。也就是说，每一次转移，函数与凸包的交点都往右移动。所以我们只需要用一个 deque 维护凸包，在队尾加直线，在队首查询，如果交点超出队首直线的管辖范围，就 pop_front。
复杂度 $O(n^2p)$。
听说有一个瞎搞做法可以拿分：在前文的基础上，dp 过程只用 double 计算，记录转移点，然后最后用高精度还原答案，复杂度 $O(n(n+p))$，但是应该是可以卡的。
状态优化
根据讲题 ppt，还有个奇妙性质，就是长度不为 1 的区间只有 $O(\log nh)$ 个。因此，数组的第一维只用开到 $\log nh$，经过实测，开到 5 就能过，$O(np\log nh)$。
此时，因为 dp 中除法的次数很少，所以用前文的瞎搞做法也是正确的，复杂度 $O(n(\log nh+p))$。
但是我不会证这个性质，看讲题 ppt，总觉得出题人的证明也不太靠谱。比如这页的不等式放缩：
按我的理解，这个不等式应该放缩出来 $l\ge$ 什么东西的。
如果哪位知道这个咋证明，或者我理解错了，还请指出。
代码
$O(np\log nh)$ 做法，省略高精度库。
|
|