题目描述
你有若干个 [1,n] 内的正整数:对于 1≤i≤n,你有 ai 个整数 i。设 S=∑i=1nai。
对于一个序列 p1,p2,⋯,pl,定义其众数 maj(p1,p2,⋯,pl) 为出现次数最多的数。若有多个数出现次数最多,则其中最大的数为其众数。
现在你需要把这 S 个数排成一个序列 b1,b2,⋯,bS,使得 ∑i=1Smaj(b1,b2,⋯,bi) 最大。输出该最大值。
输入格式
第一行一个整数 n,表示值域。
接下来一行 n 个正整数 a1,a2,⋯,an,表示每种数的个数。
输出格式
输出一行一个正整数表示 ∑i=1Smaj(b1,b2,⋯,bi) 的最大值。
3
1 3 2
17
提示
样例解释 1
一个达到最大值的序列为 (3,2,3,1,2,2)。
数据范围
对于所有测试数据,1≤n≤105,1≤a1,a2,⋯,an≤105。
题目来源
来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)初赛。