<h2>背景</h2>
<p>我一直试图通过Kattis上提供的优秀challanges来温习我的Python知识。我现在被<a href="https://open.kattis.com/problems/chopwood" rel="nofollow">this problem</a>难住了,这需要很好的效率。我的解决方案得到了正确的答案,但是太慢了。虽然其他语言可能会更快,但我从统计数据中知道,使用python3可以解决这个问题。你知道吗</p>
<h2>问题</h2>
<p>给程序一个整数长度,然后是一个包含整数值的长度列表。我将这些添加到一个列表中,但是当给我很长的列表时,程序在完成输入读取之前超过了3s的时间限制。你知道吗</p>
<p>任何关于如何加快速度的建议都将不胜感激!你知道吗</p>
<h2>到目前为止的代码(经过理解更新)</h2>
<p><a href="https://gist.github.com/anonymous/4322dff72f6e751515e2" rel="nofollow">Gist copy</a></p>
<pre><code>import collections
length = int(input())
inputList = []
maxVal = 0
# Set offers O(1) when checking if an element is present.
history = set()
results = []
impossible = False
inputList = [input() for _ in range(length)]
# Map int conversion and convert to deque for O(1) removal from left later on.
# Is this worth it?
inputDeque = collections.deque(map(int, inputList))
# Find highest value. Was doing this during input,
# moved here to potentially speed up input loop.
maxVal = max(inputDeque)
# There must be a smarter way here,
# but we're not getting this far on large inputs yet.
# For every element of input,
# find the lowest value that is not in the remaining input or history.
for _ in range(length):
for i in range(1, 200000, 1):
# If the lowest value we can get is higher than the largest input, this can't be solved.
if i >= maxVal:
impossible = True
break
if i not in history and i not in inputDeque:
results.append(i)
history.add(i)
inputDeque.popleft()
break
if impossible:
break
if impossible:
print('Error')
else:
[print(i) for i in results]
</code></pre>
<p>非常感谢!你知道吗</p>