课堂计划

## 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 指数。

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

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

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

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

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

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

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

程序填空:

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

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

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

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

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

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

# 输出最大可能的 h 指数
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 不需要清零。

N = 123456

class Cow:
    def __init__(self, f, s):
        self.f = f
        self.s = s

c = [Cow(0, 0) for _ in range(N)]
h = [0] * N
res = [0] * N
cur = 0

def solve(x, y):
    global cur
    if h[y] == 0:
        h[y] = x
        cur += 1
    elif h[y] > x:
        z = h[y]
        h[y] = x
        if y == c[z].f:
            solve(z, c[z].s)

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

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

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

if __name__ == "__main__":
    main()

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

平面上有(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