Python青铜级算法问题:逻辑在理论上是健全的，但不知道如何实现

Question

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

母牛贝茜报名参加了一个计算机科学PhD项目，这是她对计算机科学的热爱，也是有一天成为“贝西博士”的诱惑。经过一段时间的学术研究，她发表了N篇论文(1≤N≤100000)，她的第一篇论文从其他研究文献中积累了词学引文(0≤ci≤100000)。贝西听说，一个学者的成功可以用他们的h指数来衡量。H指数是最大的数h，因此研究者至少有h篇论文，每个论文至少有h引文。例如，拥有4篇论文和相应引文数(1,100, 2，3 )的研究人员的h指数为2，而如果引用数为(1,100,3,3)，则h指数为3。

为了提高她的h指数，贝茜正计划写一篇调查文章，引用她过去的几篇论文。由于页数限制，她最多可以在这次调查中引用L篇文章(0≤L≤100000)，当然，她最多只能引用一次论文。

帮助贝茜确定她写完这份调查后可能达到的最大h指数。

请注意，贝西的研究顾问可能会在某一时刻告诉她，仅仅为了提高h指数而写一份调查报告是道德上的怀疑；其他学者也不建议效仿贝西的做法。

输入格式(输入来自终端/ stdin)：

输入的第一行包含N和L，第二行包含N个分隔整数c1，…。、cN.

输出格式(打印输出到终端/标准输出)：

在撰写调查报告后，贝西指数的最大值可能达到。

样本输入

4 0
1 100 2 3

样本输出

2

贝茜不能引用她过去的任何一篇论文。如上所述，(1,100,2,3)的h指数为2.

样本输入

4 1
1 100 2 3

样本输出

3

如果贝西引用了她的第三篇论文，那么引文数就变成(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

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

注意:我也遇到了时间复杂性问题，比如当我面临一个n = 100000和l = 50000问题时。

Answer 1

在实现中有几个错误。

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

这是不正确的，因为h索引最多是引用非零引文的文章数，所以如果l>0或引文> 0，则为1，否则为0。

导致输入错误的具体问题是假设h索引必须以引用计数的形式出现；考虑具有h索引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)