Acowdemia I

题目描述

奶牛 Bessie 因为热爱计算机科学，并且憧憬有朝一日成为“Bessie 博士”，报名参加了计算机科学博士项目。经过一段时间的学术研究，她已经发表了 $N$ 篇论文（$1 \leq N \leq 10^5$），其中第 $i$ 篇论文在学术文献中被其他论文引用了 $c_i$ 次（$0 \leq c_i \leq 10^5$）。 Bessie 听说衡量一位学者成功与否的一种方式是 $h$-index。$h$-index 是满足如下条件的最大整数 $h$：该研究者至少有 $h$ 篇论文，并且这 $h$ 篇论文每篇的引用次数都至少为 $h$。例如，一位研究者有 $4$ 篇论文，其引用次数分别为 $(1,100,2,3)$，则其 $h$-index 为 $2$；而如果引用次数为 $(1,100,3,3)$，则 $h$-index 为 $3$。 为了提高自己的 $h$-index，Bessie 计划写一篇综述文章，引用她过去发表的若干论文。由于篇幅限制，这篇综述最多只能包含 $L$ 次引用（$0 \leq L \leq 10^5$），当然她对自己的每篇论文最多只能引用一次。 请帮助 Bessie 确定写完这篇综述后，她可能达到的最大 $h$-index。 注意：Bessie 的导师或许应该在某个时候告诉她，仅仅为了提高 $h$ 指数而写综述在伦理上是值得怀疑的；不建议其他学者效仿 Bessie 的做法。

输入格式

第一行输入包含 $N$ 和 $L$。 第二行包含 $N$ 个以空格分隔的整数 $c_1,\ldots, c_N$。

输出格式

输出 Bessie 写完综述后可能达到的最大 $h$-index。

4 0
1 100 2 3

2

4 1
1 100 2 3

3

提示

Bessie 不能引用她过去的任何论文。如上所述，$(1,100,2,3)$ 的 $h$-index 为 $2$。 如果 Bessie 引用她的第三篇论文，则引用次数变为 $(1,100,3,3)$。如上所述，这些引用次数的 $h$-index 为 $3$。 SCORING: 测试点 1-7 满足 $N \leq 100$。 测试点 8-10 满足 $N \leq 1000$。 测试点 11-17 满足 $N \leq 10^5$。 题目贡献：Dhruv Rohatgi

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze