题目大意

给定 $n$ 种数字，每种数字 $i$ 有 $a_i$ 个。需要将它们排成一个序列，使得每个前缀的众数（出现次数最多，平局时取数值最大）的和最大。求这个最大和。

算法思路

核心思想

贪心构造 + 后缀和优化

关键观察

数值大的数字优势：由于平局时取数值大的作为众数，所以大数值的数字有优势

构造策略：从大到小考虑数字，尽量让大数字在前缀中占据多数

数学分析：对于数字 $i$，如果它的数量 $a_i$ 能成为某个前缀的众数，那么它在这个前缀中需要严格多于所有比它大的数字

具体分析

1. 贡献计算

对于数字 $i$：

比 $i$ 大的数字有 $(n-i)$ 个

要让 $i$ 成为前缀众数，至少需要放置 $k$ 个 $i$，使得这 $k$ 个 $i$ 的数量超过所有比 $i$ 大的数字的总数

每个 $i$ 的贡献可以累加计算

2. 算法实现

从大到小处理数字（$i$ 从 $n$ 到 $1$）

维护 maxn 表示当前遇到的最大 $a_i$

sum[x] 表示当数字数量为 $x$ 时，这些数字的贡献和

对于每个 $i$，累加 sum[a[i]] 到答案

3. 公式推导

设排序后的 $a_i$ 为 $b_1 \ge b_2 \ge \cdots \ge b_n$ 最大和 = $\sum_{i=1}^n i \times \min(a_i, \text{某个上界})$ 通过维护后缀信息高效计算

算法流程

读入 $n$ 和数组 $a$

从 $i=n$ 到 $1$ 遍历：

更新 sum 数组（计算不同数量级的贡献）

累加 sum[a[i]] 到答案

输出答案

复杂度分析

时间复杂度：$O(n + \max a_i)$，线性复杂度

空间复杂度：$O(n + \max a_i)$

总结

本题的关键在于：

发现贪心性质：大数值的数字应该优先安排

数学建模：将问题转化为贡献计算

后缀优化：通过维护后缀信息避免重复计算

线性处理：在 $n \le 10^5$ 范围内高效求解