Acowdemia

题目描述

奶牛 Bessie 因为热爱计算机科学，以及有朝一日成为“Bessie 博士”的吸引力，报名参加了计算机科学博士项目。 在进行了一段时间的学术研究后，她已经发表了 $N$ 篇论文（$1 \leq N \leq 10^5$），其中第 $i$ 篇论文在研究文献中被其他论文引用了 $c_i$ 次（$0 \leq c_i \leq 10^5$）。 Bessie 听说衡量一位学者成功与否的指标之一是 $h$ 指数。$h$ 指数是最大的整数 $h$，使得研究者至少有 $h$ 篇论文，并且这些论文每篇的引用次数都至少为 $h$。例如，一位研究者有 $4$ 篇论文，引用次数分别为 $(1,100,2,3)$，则其 $h$ 指数为 $2$；而如果引用次数为 $(1,100,3,3)$，则 $h$ 指数为 $3$。 为了提高她的 $h$ 指数，Bessie 计划撰写最多 $K$ 篇综述文章（$0 \leq K \leq 10^5$），每篇综述都会引用她过去的许多论文。然而，由于页数限制，她在每篇综述中最多只能引用 $L$ 篇论文（$0 \leq L \leq 10^5$）。当然，在同一篇综述中，同一篇论文不能被引用多次（但一篇论文可以在多篇综述中被引用）。 请帮助 Bessie 确定在撰写这些综述文章之后，她可能达到的最大 $h$ 指数。Bessie 不允许在她的某篇综述中引用另一篇综述。 注意：Bessie 的导师可能应该在某个时候告诉她，仅仅为了提高 $h$ 指数而写综述在伦理上是值得商榷的；不建议其他学者效仿 Bessie 的做法。

输入格式

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

输出格式

输出一行，表示最大的 $h$ 指数。

4 4 1
1 100 1 1

3

4 1 4
1 100 1 1

2

提示

在此示例中，Bessie 最多可以写 $4$ 篇综述文章，每篇最多引用 $1$ 篇论文。 如果她将她的第一篇和第三篇论文各引用两次，那么她的 $h$ 指数变为 $3$。 在第二个示例中，Bessie 最多只能写一篇文章。如果 Bessie 至少引用一次她的第一、第三或第四篇论文中的任意一篇，那么她的 $h$ 指数变为 $2$。 评分： 测试点 1-6 满足 $N\le 100$。 测试点 7-16 没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2021|Silver

来源

USACO|2021|Silver