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

Question

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

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

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

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

请注意，Bessie 的研究顾问可能应该在某个时候通知她，仅仅为了增加一个人的 h 指数而编写调查在道德上是可疑的；不建议其他学者在这里效仿 Bessie 的例子。

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

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

输出格式（将输出打印到终端/stdout）：

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

样本输入:

4 0
1 100 2 3

样本输出：

Bessie 无法 ci提交她过去的任何论文。如上所述，(1,100,2,3) 的 h-index 为 2.

样本输入:

4 1
1 100 2 3

样本输出：

如果 Bessie ci测试她的第三篇论文，那么 citation 计数变为 (1,100,3,3)。如上所述，这些计数的 h-index 为 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

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

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

注意：我也有时间复杂度的问题，当我遇到 n = 100000 和 l = 50000.

的问题时

Answer 1

执行中有几个错误，例如

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

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

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

另一个主要问题是在主循环中使用 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)

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

Python USACO Bronze Level Algorithm Problem: Logic is Sound in Theory, but do not Know how to Implement

python

algorithm

optimization

logic