题解：CF1610E AmShZ and G.O.A.T.

· · 题解

\tt{Solution}

最少删除元素个数转化为最多保留元素个数。考虑不合法序列的性质。发现严格大于平均数的元素个数与严格小于平均数元素个数的关系可以与该序列中点位置的数联系在一起，显然的，对于 \{c_k\}，该序列是不合法的，则有 c_{\left \lceil \frac{k}{2} \right \rceil} > \frac{\sum c_i}{k}。

考虑更简化的情况，对于 k = 1,2 的情况，序列一定是好的。对于 k = 3，据上式可得 2 \cdot c_2 > c_1 + c_3 等价于该序列是坏的。此处存在一个结论：一个序列是好的，充要条件是不存在长度为 3 的子序列是不合法的。首先考虑对于一个不合法的序列，若其不存在长度为 3 的不合法子序列，则 \forall i,c_i + c_{k - i + 1} \ge 2 \cdot c_{\left \lceil \frac{k}{2} \right \rceil}，对其求和有 \sum\limits_{i = 1}^{k} c_i + c_{k - i + 1} \ge c_{\left \lceil \frac{k}{2} \right \rceil} \cdot 2k，化简式子得到 c_{\left \lceil \frac{k}{2} \right \rceil} \le \frac{\sum c_i}{k}，因为该序列是不合法的，所以应有 c_{\left \lceil \frac{k}{2} \right \rceil} > \frac{\sum c_i}{k}，矛盾。

得证一个不合法的序列一定存在长度为 3 的不合法子序列，故一个坏的序列一定存在长度为 3 的不合法子序列，反之若不存在长度为 3 的不合法子序列，该序列一定不是坏的，即是好的。充要性得证。

所以判断当前序列是否是好的，只需要检查是否存在长度为 3 的子序列不合法即可。贪心地去考虑，每次钦定最终序列的最小值 mn，将原序列最大值加入，令其为 p，此时只需要找到最大的 mn \le c_i \le \frac{mn + p}{2}，则可以将 c_i 加入，并令 p = c_i，重复该二分过程，这样构造出的答案一定不劣。

时间复杂度 \mathcal{O}(n \log V \log n)，因为每次加入 c_i 更新后 p 至少减半，存在一只 \log V。