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 11 problem, during the second day — exactly 22 problems, during the third day — exactly 33 problems, and so on. During the kk-th day he should solve kk problems.

Polycarp has a list of nn contests, the ii-th contest consists of aia_i problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly kk problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least kk problems that Polycarp didn't solve yet during the kk-th day, then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?

Polycarp 希望在另一场编程竞赛前进行训练。在训练的第一天,他必须恰好解决 11 道题;第二天恰好解决 22 道题;第三天恰好解决 33 道题;依此类推。在第 kk 天,他必须恰好解决 kk 道题。

Polycarp 有一个包含 nn 场比赛的列表,其中第 ii 场比赛包含 aia_i 道题。每天,Polycarp 必须从他尚未解决过的比赛中恰好选择一场,并解决其中的 kk 道题(第 kk 天)。该比赛中的其余题目将被丢弃。如果在第 kk 天,不存在任何尚未解决且题目数量不少于 kk 道的比赛,则 Polycarp 将停止训练。

如果 Polycarp 最优地选择比赛,他最多能训练多少天?

输入格式

The first line of the input contains one integer nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) — the number of contests.

The second line of the input contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤2⋅1051 \le a_i \le 2 \cdot 10^5) — the number of problems in the ii-th contest.

输入的第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)—— 表示比赛的场数。

输入的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤2⋅1051 \le a_i \le 2 \cdot 10^5)—— 表示第 ii 场比赛中题目的数量。

输出格式

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测评打分。不知道怎么写?

首页