题解：AT_arc197_b [ARC197B] Greater Than Average

wl2009 · 2025-05-08 10:30:55 · 题解

首先肯定要将 x 排序。

我们钦定 x_i 是比平均数 v 大的最小的数，则 x_1 一直到 x_{i - 1} 全部选上一定是最优的，因为它们不会使 v 增大，而比 v 大的数肯定是选较小的，因为我们不希望 v 超过 x_i。所以最优子序列一定是 x 的一个前缀。

时间复杂度 O(n \log n)，瓶颈在于排序。