python - Python USACO 青铜级算法题：逻辑在理论上是合理的，但不知道如何实现

Question

我正在为即将在 12 月举行的 USACO 比赛练习，并试图解决这个问题：http ://www.usaco.org/index.php?page=viewproblem2&cpid=1131

母牛 Bessie 参加了计算机科学博士课程，她对计算机科学的热爱以及有一天成为“Bessie 博士”的诱惑力。经过一段时间的学术研究，她现已发表N篇论文（1≤N≤100000），第i篇论文在研究文献中积累了其他论文的ci引用（0≤ci≤100000）。Bessie 听说一个学者的成功可以通过他们的 h 指数来衡量。h-index 是最大的数 h，使得研究人员至少有 h 篇论文，每篇论文至少有 h 次引用。例如，有 4 篇论文和各自的引用计数 (1,100,2,3) 的研究人员的 h-index 为 2，而如果引用计数为 (1,100,3,3)，则 h-index 将为 3。

为了提高她的 H 指数，Bessie 计划撰写一篇调查文章，引用她过去的几篇论文。由于页数限制，她在本次调查中最多可以包含 L 次引用（0≤L≤100000），当然她的每篇论文最多只能引用一次。

帮助 Bessie 确定她在完成这份调查后可能达到的最大 h 指数。

请注意，Bessie 的研究顾问可能应该在某个时候告诉她，仅仅为了提高一个人的 h 指数而编写一份调查在道德上是有问题的；不建议其他学者在这里效仿贝西的例子。

输入格式（输入来自终端/标准输入）：

输入的第一行包含 N 和 L。第二行包含 N 个空格分隔的整数 c1,…,cN。

输出格式（打印输出到终端/标准输出）：

完成调查后，Bessie 可能达到的最大 h 指数。

样品输入：

4 0
1 100 2 3

样品输出：

2

贝西不能引用她过去的任何论文。如上所述，(1,100,2,3) 的 h-index 为 2。

样品输入：

4 1
1 100 2 3

样品输出：

3

如果 Bessie 引用了她的第三篇论文，则引用计数变为 (1,100,3,3)。如上所述，这些计数的 h 指数为 3。

评分：

• 测试用例 1-7 满足 N≤100。
• 测试用例 8-10 满足 N≤1000。
• 测试用例 11-17 满足 N≤100000。

我针对这个问题的 Python 3 代码：

# read data and sort list
line = input().strip().split()
n, l = int(line[0]), int(line[1])
cite = [int(i) for i in input().strip().split()]
cite.sort()

# initiate the integer that will keep track of the largest number that satisfies the conditions and the set we will use to check whether or not a number has already been checked
max_num = 0
nums = set()

# iterate over every number
for i in range(n):
    if cite[i] in nums:
        # skip the iteration if the number has already been checked
        continue
    # add the number to the set
    nums.add(cite[i])
    # if any numbers are 1 less than the current number, keep track of them to add later on in the program. set extra to l if there are more numbers that are less than the current number that citations to be used.
    if cite.count(cite[i]-1) <= l:
        extra = cite.count(cite[i]-1)
    else:
        extra = l
    # check if the h-index is greater than the currently largest h-index and replace it if it is.
    if len(cite[i:]) + extra >= cite[i] and cite[i] >= max_num:
        max_num = cite[i]

# for a list of citations that only have 1 integer in it, check if l is > 0. if it is, the max number is that number + 1.
if n == 1 and l > 0:
    max_num = cite[0] + 1

print(max_num)

我相信逻辑是正确的，但是当输入是

1000 251
500 500 500 500 500 502 500 502 500 502 500 500 500 500 500 500 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 502 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 502 500 500 500 500 500 502 500 500 500 500 500 502 502 500 502 500 500 500 500 502 502 502 500 500 500 500 500 502 502 502 500 500 500 500 502 500 500 500 500 500 500 500 500 502 500 500 500 500 500 500 500 500 500 500 502 500 500 502 500 500 500 500 500 500 500 500 502 502 500 500 502 500 500 500 502 500 500 502 502 500 500 500 502 500 500 502 500 500 500 502 502 500 500 500 500 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 500 502 502 500 500 500 500 500 502 502 502 500 500 502 500 500 500 500 500 500 500 500 502 500 500 500 500 500 502 502 500 502 500 502 500 500 500 500 500 502 502 500 500 502 500 502 502 500 500 502 500 500 502 500 500 502 500 500 502 500 500 502 500 500 500 500 500 500 500 500 502 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 502 502 502 500 500 500 502 500 500 500 500 502 500 500 500 502 502 502 502 500 500 500 500 500 500 500 500 500 500 502 500 502 500 502 502 500 502 500 500 500 500 500 502 500 500 500 500 500 502 500 500 500 500 502 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 502 500 500 500 500 502 502 500 502 502 500 500 500 502 502 500 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 502 502 500 502 502 500 500 500 500 500 502 500 502 500 500 500 500 500 502 500 500 500 500 500 502 502 502 500 500 500 500 500 500 502 502 500 500 500 502 500 500 502 500 500 502 500 500 500 502 502 500 502 500 500 500 500 500 500 500 500 500 500 500 500 500 502 502 500 502 500 502 502 500 500 500 500 500 500 500 500 502 500 502 500 500 502 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 502 502 500 500 500 500 502 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 502 502 500 502 500 502 502 500 500 502 500 502 502 500 502 500 500 500 500 500 502 500 502 500 500 500 500 500 500 500 500 500 502 500 500 500 500 500 502 502 502 502 502 500 500 502 500 502 500 500 502 500 500 500 500 500 500 502 502 500 500 502 500 500 500 500 500 500 500 500 500 500 500 502 500 500 502 500 500 502 500 500 500 500 500 502 500 500 500 500 500 500 502 500 502 500 500 500 500 500 500 502 502 500 502 502 500 502 500 500 500 500 500 500 500 502 500 502 500 502 502 500 500 500 500 500 500 502 502 502 500 500 500 500 500 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 502 500 500 502 502 502 500 500 500 500 500 502 500 502 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 502 500 502 500 502 502 500 500 500 500 500 500 502 502 500 500 502 500 500 500 500 500 500 500 500 500 502 500 500 500 502 502 500 502 500 502 502 500 500 500 500 502 502 502 502 500 500 500 502 500 500 500 500 500 500 500 500 502 500 502 500 500 502 500 502 500 500 500 500 500 502 500 500 500 500 502 500 500 502 500 502 502 500 502 500 500 500 500 500 500 500 502 500 500 502 500 500 502 500 500 500 500 500 502 502 500 500 500 500 500 500 500 502 500 500 500 500 500 502 502 500 500 502 502 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 502 500 502 502 500 500 500 500 502 500 500 500 502 500 500 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 500 500 500 502 500 500 500 502 500 500 500 500 500 500 500 500 500 500 502 500 500 500 500 500 500 500 502 502 502 502 500 500 500 500 502 500 502 500 500 500 500 500 500 502 502 500 502 500 500 500 502 500 500 500 500 500 500 500 500 500 502 500 500 500 500 500 500 500 500 502 500 500 502 502 500 500 502 500 500 500 502 502 500 500 500 502 500 502 500 500 502 500 500 500 502 500 500 500 500 500 500 502 500 500 500 500 502 502 500 502 500 500 502 500 500 500 500 500 500 500 502 500 502 500 502 500 500 502 500 500 500 500 502 502 500 500

它返回错误的答案。它打印500但应该是501

我的实现是否有错误，还是我的逻辑有问题？

注意：我也遇到了时间复杂度的问题，比如当我遇到 wheren = 100000和l = 50000.

标签： pythonalgorithmoptimizationlogic

Answer 1

实现中有几个错误，例如

if n == 1 and l > 0:
    max_num = cite[0] + 1

这是不正确的，因为 h-index 至多是非零引用的论文数量，所以如果 l > 0 或 cite[0] > 0 则为 1，否则为 0。

导致输入错误的具体问题是假设 h 索引必须作为引用计数出现；考虑具有 h-index 3 的 [4, 4, 4]。

另一个主要问题是在主循环中使用 list.count()，而不是使用计数器或其他哈希映射。使用计数器，您甚至不需要对数组进行排序；只需跟踪有多少论文仍未被看到。

import collections
line = input().strip().split()
n, l = int(line[0]), int(line[1])
cite = [int(i) for i in input().strip().split()]

max_num = 0
citation_counts = collections.Counter(cite)
remaining = n


for i in range(n+1):

    extra = min(citation_counts[i - 1], l)
    if extra + remaining >= i:
        max_num = i

    remaining -= citation_counts[i]

print(max_num)