读取每篇论文的引用次数，并按降序排序

## USACO 2021 US Open, Silver Problem 3. Acowdemia

https://usaco.org/index.php?page=viewproblem2&cpid=1136

我们需要找到最大的 h 指数，即至少有 h 篇论文，每篇至少有 h 次引用。Bessie 可以通过调查文章增加引用次数，每篇调查文章最多引用 L 篇论文，总共可以写 K 篇调查文章。

首先，将论文的引用次数降序排序，这样可以优先处理引用次数高的论文，减少需要增加的引用次数。

然后使用二分查找来确定最大可能的 h 值。我们在 0 到 n 之间查找，通过中间值来验证是否能达到某个 h 指数。

检查函数 ok(h) 用于验证是否能通过增加引用次数达到某个 h 指数。它统计当前已经有至少 h 次引用的论文，对于不足 h 次引用的论文，计算需要补充的引用次数，并检查总的可用引用次数是否足够。

这种方法通过二分查找高效地逼近最大可能的 h，并确保找到了在给定约束下的最大 h 指数。

1
n, k, L = map(int, input().split())
2

3
# 读取每篇论文的引用次数，并按降序排序
4
c = sorted(list(map(int, input().split())), reverse=True)
5

6
# 定义一个函数来检查是否可以达到给定的 h 指数
7
def ok(h):
8
    cnt = 0  # 记录至少有 h 次引用的论文数量
9
    tot = k * L  # 可以分配的总额外引用次数（k 篇调查，每篇 L 次引用）
10

11
    # 遍历每篇论文的引用次数
12
    for x in c:
13
        if x >= h:
14
            cnt += 1  # 如果该论文引用次数已经至少是 h，计入满足条件的论文数
15
            continue
20 collapsed lines
16
        # 计算该论文需要的额外引用次数以达到 h 次引用
17
        if h - x <= tot and h - x <= k:
18
            tot -= h - x  # 使用额外的引用次数
19
            cnt += 1  # 计入满足条件的论文数
20

21
    # 返回是否有至少 h 篇论文满足条件
22
    return cnt >= h
23

24
# 二分查找来确定最大可能的 h 指数
25
l, r, ans = 0, n, -1
26
while l <= r:
27
    mid = (l + r) // 2
28
    if ok(mid):
29
        ans = mid  # 如果当前的 h 可行，尝试更大的 h
30
        l = mid + 1
31
    else:
32
        r = mid - 1  # 如果当前的 h 不可行，尝试更小的 h
33

34
# 输出最大可能的 h 指数
35
print(ans)

程序填空:

1
n, k, L = map(int, input().split())
2

3
# 读取每篇论文的引用次数，并按降序排序
4
c = ___
5

6
# 定义一个函数来检查是否可以达到给定的 h 指数
7
def ok(h):
8
    cnt = 0  # 记录至少有 h 次引用的论文数量
9
    tot = ___  # 可以分配的总额外引用次数（k 篇调查，每篇 L 次引用）
10

11
    # 遍历每篇论文的引用次数
12
    for x in c:
13
        if x >= h:
14
            ___  # 如果该论文引用次数已经至少是 h，计入满足条件的论文数
15
            continue
20 collapsed lines
16
        # 计算该论文需要的额外引用次数以达到 h 次引用
17
        if h - x <= tot and h - x <= k:
18
            tot -= ___  # 使用额外的引用次数
19
            cnt += 1  # 计入满足条件的论文数
20

21
    # 返回是否有至少 h 篇论文满足条件
22
    return cnt >= h
23

24
# 二分查找来确定最大可能的 h 指数
25
l, r, ans = 0, n, -1
26
while l <= r:
27
    mid = ___
28
    if ___:
29
        ans = mid  # 如果当前的 h 可行，尝试更大的 h
30
        ___
31
    else:
32
        r = mid - 1  # 如果当前的 h 不可行，尝试更小的 h
33

34
# 输出最大可能的 h 指数
35
print(ans)

P6282 [USACO20OPEN] Cereal S

https://usaco.org/index.php?page=viewproblem2&cpid=1039

如果我们增加奶牛，即倒着求每个答案，最后倒着输出就行了。

如果增加一头奶牛，又会出现什么情况呢？

如果它最喜欢的麦片没有被选择，那么它就会选它，且不影响其他奶牛；
如果它最喜欢的麦片被选择，因为它的优先级比其他牛都高，所以会把其他牛的麦片“抢”过来，其他牛只能“退而求其次”。

递归求解即可，因为所有奶牛最多选两次，所以 solvesolve 函数的复杂度是 Θ(1)Θ(1) 的，整个代码的时间复杂度为 Θ(N)Θ(N)。

实现方法见代码注释：

cici 表示第 ii 头奶牛的喜好，hihi 表示拿走第 ii 种麦片的牛的编号，resiresi 表示移走 i−1i−1 头牛的答案，curcur 是计算答案的计数器。

因为领麦片的牛越多，领到麦片的牛就越多，所以越往后面，curcur 就越大，故每次计算的时候 curcur 不需要清零。

1
N = 123456
2

3
class Cow:
4
    def __init__(self, f, s):
5
        self.f = f
6
        self.s = s
7

8
c = [Cow(0, 0) for _ in range(N)]
9
h = [0] * N
10
res = [0] * N
11
cur = 0
12

13
def solve(x, y):
14
    global cur
15
    if h[y] == 0:
24 collapsed lines
16
        h[y] = x
17
        cur += 1
18
    elif h[y] > x:
19
        z = h[y]
20
        h[y] = x
21
        if y == c[z].f:
22
            solve(z, c[z].s)
23

24
def main():
25
    global cur
26
    n, m = map(int, input().split())
27
    for i in range(1, n + 1):
28
        f, s = map(int, input().split())
29
        c[i] = Cow(f, s)
30

31
    for i in range(n - 1, -1, -1):
32
        solve(i + 1, c[i + 1].f)
33
        res[i + 1] = cur
34

35
    for i in range(1, n + 1):
36
        print(res[i])
37

38
if __name__ == "__main__":
39
    main()

https://www.luogu.com.cn/problem/P2997

1
平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内

读取每篇论文的引用次数，并按降序排序

## USACO 2021 US Open, Silver Problem 3. Acowdemia

P6282 [USACO20OPEN] Cereal S

作业题 # P2997 [USACO10NOV] Banner S