CF1165B.Polycarp Training
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly 1 problem, during the second day — exactly 2 problems, during the third day — exactly 3 problems, and so on. During the k-th day he should solve k problems.
Polycarp has a list of n contests, the i-th contest consists of ai problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly k problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least k problems that Polycarp didn't solve yet during the k-th day, then Polycarp stops his training.
How many days Polycarp can train if he chooses the contests optimally?
Polycarp 希望在另一场编程竞赛前进行训练。在训练的第一天,他必须恰好解决 1 道题;第二天恰好解决 2 道题;第三天恰好解决 3 道题;依此类推。在第 k 天,他必须恰好解决 k 道题。
Polycarp 有一个包含 n 场比赛的列表,其中第 i 场比赛包含 ai 道题。每天,Polycarp 必须从他尚未解决过的比赛中恰好选择一场,并解决其中的 k 道题(第 k 天)。该比赛中的其余题目将被丢弃。如果在第 k 天,不存在任何尚未解决且题目数量不少于 k 道的比赛,则 Polycarp 将停止训练。
如果 Polycarp 最优地选择比赛,他最多能训练多少天?
输入格式
The first line of the input contains one integer n (1≤n≤2⋅105) — the number of contests.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤2⋅105) — the number of problems in the i-th contest.
输入的第一行包含一个整数 n(1≤n≤2⋅105)—— 表示比赛的场数。
输入的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤2⋅105)—— 表示第 i 场比赛中题目的数量。
输出格式
Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.
输出一个整数——Polycarp 在最优选择比赛的情况下最多可以训练的天数。
输入输出样例
输入#1
4 3 1 4 1
输出#1
3
输入#2
3 1 1 1
输出#2
1
输入#3
5 1 1 1 2 2
输出#3
2
输入解题思路,AI测评打分。不知道怎么写?