3745. 牛的学术圈 I - AcWing题库

题目

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

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

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

$h$ 指数等于使得研究员有至少 hh 篇引用次数不少于 $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≤1051≤N≤105,
0≤ci≤1050≤ci≤105,
0≤L≤105

输入样例1：

4 0
1 100 2 3

输出样例1：

2

样例1解释

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

输入样例2：

4 1
1 100 2 3

输出样例2：

3

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

思路

二分

看到题眼

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

不少于(大于)xxx的最大(小)值，这是二分的经典描述，由于求的是$h$,我们考虑在答案上二分

思考步骤

1.是否可以二分

观察答案是否具有二段性(单调性)

用样例2解释：在答案为3时，h取小于3的数，满足题意(是合法的但不是最大的)，取大于3的数一定不合法

所以可以用二分.ﾟヽ(｡◕‿◕｡)ﾉﾟ

2.二分的范围

显然，h的上界为 $N$

3.思考check函数怎么写

当答案固定为mid时，由于她只能引用每篇她的论文至多一次，统计一下数组中大于等于mid的数的个数，如果不足

可以在小于等于mid的数中找值为mid-1的数的个数，这些数可以通过消耗一次引用,即L-1,变为合法;如果在以上操作中答案仍然不合法，此答案不合法

代码

可以去看其他大佬

贪心

让我们通过样例来思考贪心方案，观察样例，思考如何操作，才能让答案最大？

结论：让数组中的所有数全部相等，答案最大，可以取到数组长度$N$

由此，我们构想一种贪心方案：

1.统计出每个数出现的次数。因为她只能引用每篇她的论文至多一次，进行引用操作的时候必然要用到这个次数

2.从小往大枚举答案，累加一下当前答案的引用次数