Cow College

题目描述

Farmer John 正计划为奶牛开办一所新的大学！ 有 $N$（$1 \le N \le 10^5$）头奶牛可能会就读这所大学。每头奶牛愿意支付的最高学费为 $c_i$（$1 \le c_i \le 10^6$）。Farmer John 可以设置一个所有奶牛入学都必须支付的学费。如果该学费高于某头奶牛愿意支付的最高学费，那么这头奶牛就不会入学。Farmer John 希望赚到尽可能多的钱，以便给讲师支付公平的工资。 请确定他最多能赚多少钱，以及他应该收取多少学费。

输入格式

第一行包含 $N$。 第二行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$，其中 $c_i$ 是第 $i$ 头奶牛愿意支付的最高学费。

输出格式

请输出 Farmer John 能赚到的最大金额以及他应收取的最优学费。如果存在多个解，输出最优学费最小的那个解。 注意：本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 Java 中的 "long"，或 C/C++ 中的 "long long"）。

4
1 6 4 6

12 4

提示

如果 Farmer John 收取 $4$，则会有 $3$ 头奶牛入学，因此他可以赚到 $3 \cdot 4 = 12$。 SCORING: 测试点 2 到 4 满足 $c_i \le 1{,}000$。 测试点 5 到 8 满足 $N \le 5{,}000$。 测试点 9 到 12 没有额外限制。 题目来源：Freddie Tang

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze