T1:Cow College
总学费 \(=\) 设置的单人学费 \(\times\) 接受的奶牛数
一旦固定单人学费,就能确定接受的奶牛数
单人学费可以是哪些值?
\(\{c_1, c_2, \cdots, c_n\}\) 其中之一作为学费门槛
暴力做法是先枚举单人学费是多少,再查看每个人的可接受学费是否大于等于单人学费,复杂度为 \(O(n^2)\)
可以通过对序列 \(c\) 做降序排序来优化掉第二重循环
代码实现
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
tot, ans = 0, 0
for i in range(n):
if (i+1)*c[i] >= tot:
tot = (i+1)*c[i]
ans = c[i]
print(tot, ans)