题目名称 | 3819. [USACO Dec22 Bronze]Cow College |
---|---|
输入输出 | prob1_bronze_22dec.in/out |
难度等级 | ☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 12 |
题目来源 | Benjamin 于2022-12-24加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:1, 提交:1, 通过率:100% | ||||
Benjamin | 100 | 0.344 s | 0.00 MiB | C++ |
关于 Cow College 的近10条评论(全部评论) |
---|
prob1_bronze_22dec.in
输出文件:prob1_bronze_22dec.out
简单对比Farmer John 计划为奶牛们新开办一所大学!
有 $N(1≤N≤10^5)$ 头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费 $(1≤c_i≤10^6$)。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额,那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱,从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量,以及此时应当收取多少学费。
输入的第一行包含 $N$。
第二行包含 $N$ 个整数 $c_1,c_2,…,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⋅4=12$ 的金额。
测试点 $2-4$ 满足 $c_i ≤ 1,000$。
测试点 $5-8$ 满足 $N ≤ 5,000$。
测试点 $9-12$ 没有额外限制。
Freddie Tang