摘要
Title: 3745. 牛的学术圈 I
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms

3745. 牛的学术圈 I

题意

由于对计算机科学的热爱，以及有朝一日成为「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 的行为。
思路

题目相当于问，数组中至少h个不少于h的数，问h最大多少，期间可以给每个数最多加1，一共l次机会
将数组排序后，直接二分即可，h最小1，最大n，每次从大到小，让小于h的加1，看是否符合

代码

'''
Author: NEFU AB-IN
Date: 2022-03-17 10:53:36
FilePath: \ACM\Acwing\3745.py
LastEditTime: 2022-03-17 10:53:38
'''


def check(h, p):
    ans = 0
    for i in range(n - 1, -1, -1):
        if nums[i] >= h:
            ans += 1
        else:
            if p > 0 and nums[i] + 1 >= h:
                ans += 1
                p -= 1
            else:
                break
    return ans >= h


def find():
    # 二分h
    l, r = 1, n
    while l < r:
        mid = l + r + 1 >> 1
        if check(mid, L):
            l = mid
        else:
            r = mid - 1
    return r


n, L = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()

print(find())

3745. 牛的学术圈 I

题意

思路

代码