问题 I: Acowdemia I 牛的学术圈 I

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:120 通过:33

题目描述

由于对计算机科学的热爱,以及有朝一日成为 「Bessie 博士」的诱惑,奶牛 Bessie 开始攻读计算机科学博士学位。

经过一段时间的学术研究,她已经发表了 N 篇论文,并且她的第 i 篇论文得到了来自其他研究文献的 ci 次引用。

Bessie 听说学术成就可以用 h 指数来衡量。

h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h

例如,如果一名研究员有 4 篇论文,引用次数分别为 (1,100,2,3),则h 指数为 2,然而若引用次数为 (1,100,3,3) 则 h 指数将会是 3

为了提升她的 h 指数,Bessie 计划写一篇综述,并引用一些她曾经写过的论文。

由于页数限制,她至多可以在这篇综述中引用 L 篇论文,并且她只能引用每篇她的论文至多一次

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑;我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L

第二行包含 N 个空格分隔的整数c1,…,cN

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

数据范围

1≤N≤105,
0≤ci≤105,
0≤L≤105

输入样例1:

4 0
1 100 2 3

输出样例1:

2

样例1解释

Bessie 不能引用任何她曾经写过的论文。上文中提到,)(1,100,2,3) 的 hh 指数为 2

输入样例2:

4 1
1 100 2 3

输出样例2:

3

如果 Bessie 引用她的第三篇论文,引用数会变为 (1,100,3,3)。上文中提到,这一引用数的 h 指数为 3




Bessie the cow has enrolled in a computer science PhD program, driven by her love of computer science and also the allure of one day becoming "Dr. Bessie". Having worked for some time on her academic research, she has now published NN papers (1≤N≤1051≤N≤105), and her ii-th paper has accumulated cici citations (0≤ci≤1050≤ci≤105) from other papers in the research literature.

Bessie has heard that an academic's success can be measured by their hh-index. The hh-index is the largest number hh such that the researcher has at least hh papers each with at least hh citations. For example, a researcher with 44 papers and respective citation counts (1,100,2,3)(1,100,2,3) has an hh-index of 22, whereas if the citation counts were (1,100,3,3)(1,100,3,3) then the hh-index would be 33.

To up her hh-index, Bessie is planning to write a survey article citing several of her past papers. Due to page limits, she can include at most LL citations in this survey (0≤L≤1050≤L≤105), and of course she can cite each of her papers at most once.

Help Bessie determine the maximum hh-index she may achieve after writing this survey.

Note that Bessie's research advisor should probably inform her at some point that writing a survey solely to increase one's hh index is ethically dubious; other academics are not recommended to follow Bessie's example here.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN and LL. The second line contains NN space-separated integers c1,…,cNc1,…,cN.

OUTPUT FORMAT (print output to the terminal / stdout):

The maximum hh-index Bessie may achieve after writing the survey.

SAMPLE INPUT:

4 0
1 100 2 3

SAMPLE OUTPUT:

2

Bessie cannot cite any of her past papers. As mentioned above, the hh-index for (1,100,2,3)(1,100,2,3) is 22.

SAMPLE INPUT:

4 1
1 100 2 3

SAMPLE OUTPUT:

3

If Bessie cites her third paper, then the citation counts become (1,100,3,3)(1,100,3,3). As mentioned above, the hh-index for these counts is 33.

SCORING:

  • Test cases 1-7 satisfy N≤100N≤100.
  • Test cases 8-10 satisfy N≤1000N≤1000.
  • Test cases 11-17 satisfy N≤105N≤105.

Problem credits: Dhruv Rohatgi

输入样例 复制


输出样例 复制