PythonUSACO銅級演算法問題：理論上邏輯合理，但不知道如何實作 -有解無憂

我正在為即將在12月舉行的USACO比賽進行練習，并試圖解決這個問題：http://www.usaco.org/index.php?page=viewproblem2&cpid=1131/a>

奶牛Bessie報考了計算機科學博士課程，這是因為她對計算機科學的熱愛，同時也是因為有朝一日成為 "Bessie博士 "的誘惑。經過一段時間的學術研究，她現在已經發表了N篇論文（1≤N≤100000），她的第i篇論文已經積累了來自研究文獻中其他論文的ci參考（0≤ci≤100000）。 Bessie聽說，一個學者的成功可以用他們的h-index來衡量。h-指數是最大的數字h，即研究者至少有h篇論文，每篇論文至少有h次參考。例如，一個擁有4篇論文的研究人員，其各自的參考次數為（1,100,2,3），其h指數為2，而如果參考次數為（1,100,3,3），那么h指數將為3。

為了提高她的h指數，Bessie正計劃寫一篇調查文章，參考她過去的幾篇論文。由于篇幅限制，她最多可以在這個調查中參考L次（0≤L≤100000），當然她最多可以參考她的每篇論文一次。

請幫助Bessie確定她在寫完這份調查報告后可能達到的最大h指數。

注意，Bessie的研究顧問也許應該在某個時候告訴她，僅僅為了提高自己的h指數而撰寫調查報告在道德上是可疑的；不建議其他學者在這里效仿Bessie的例子。

輸入格式（輸入來自終端/stdin）：

第一行輸入包含 N 和 L。第二行包含N個空格分隔的整數c1,...,cN。

OUTPUT格式（列印輸出到終端/stdout）：

寫完調查后，Bessie可能達到的最大h-index。

示例輸入:

4 0
1 100  2  3

示例輸出：

Bessie不能參考她過去的任何論文。如上所述，（1,100,2,3）的h指數是2。

示例輸入：

4 1
1 100  2  3

示例輸出：

如果Bessie參考了她的第三篇論文，那么參考次數就變成了（1,100,3,3）。如上所述，這些計數的h指數是3。

參考：

我對這個問題的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()] 。
cite.sort()

# 啟動整數，它將記錄滿足條件的最大數字，以及我們將用來檢查一個數字是否已經被檢查的集合。
max_num =0
nums = set()

# 遍歷每個數字 
for i in range（n）。
    if cite[i] in nums:
        # skip the iteration if the number has already been checked.
        continue
    # 將數字添加到集合中。
    nums.add(cite[i])
    # 如果有任何數字比當前的數字少1，請記住它們，以便在程式中稍后添加。如果有更多的數字比當前的數字少，則將extra設定為l，以便使用。
    if cite.count(cite[i]-1) <= l。
        extra = cite.count(cite[i]-1)
    else:
        extra = l
    # 檢查h-index是否大于當前最大的h-index，如果是，則替換它。
    if len(cite[i:])   extra >= cite[i] and cite[i] >= max_num。
        max_num = cite[i]

# 對于一個只有1個整數的引文串列，檢查l是否為>0.如果是，最大數字就是這個數字 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 500500 500 502 502 500 500 500 500 500 502 502 502 500 500 502 500 500 500500 500 500 500 500 502 500 500 500500 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 500502 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 500500 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 500500 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 500502 500 502 502 500 500 502 500 502502 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 500500 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 500502 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 500502 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 500500 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 500502 500 500 500 502 500 500 500 500 500 500 500 500 500 502 500 500 500 500500 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的問題時。

uj5u.com熱心網友回復：

實作中存在幾個錯誤，例如：

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

這是不正確的，因為h-index最多是有非零參考的論文數量，所以如果l > 0或cite[0] > 0，它將是1，否則就是0。

導致該輸入錯誤的具體問題是假設h指數必須以參考次數的形式出現；考慮[4，4，4]，它的h指數是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)
剩余 = n


for i in range（n 1）。

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

    剩余 -= citation_counts[i]

print(max_num)

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/325798.html

標籤：

上一篇：用特定的調色板在C#中實作Floyd-Steinberg抖動

下一篇：操作json，按key值洗掉一組中的兩項