读取每篇论文的引用次数，并按降序排序
2024-11-06
241102julyfunnoteswilliam工作## USACO 2021 US Open, Silver Problem 3. Acowdemiahttps://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 Shttps://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()
作业题 # P2997 [USACO10NOV] Banner Shttps://www.luogu.com.cn/problem/P2997平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围