Python 列表排序与模拟优化问题
Python list sort and simulation optimization problem
我再次尝试解决一个问题来为即将到来的 USACO 比赛练习,但我无法满足 1 秒的时间限制:https://open.kattis.com/contests/v4xrif/problems/knigsoftheforest
All moose are knigs of the forest, but your latest moose-friend,
Karl-Älgtav, is more interesting than most. In part because of his
fondness of fermented blueberries, and in part because of the tribe he
lives in. Each year his tribe holds a tournament to determine that
year’s alpha-moose. The winner gets to lead the tribe for a year, and
then permanently leaves the tribe. The pool of contenders stays
constant over the years, apart from the old alpha-moose being replaced
by a newcomer in each tournament.
Karl-Älgtav has recently begun to wonder when it will be his turn to
win, and has asked you to help him determine this. He has supplied a
list of the strength of each of the other moose in his tribe that will
compete during the next n−1 years, along with their time of entry into
the tournament. Assuming that the winner each year is the moose with
greatest strength, determine when Karl-Älgtav becomes the alpha-moose.
Input The first line of input contains two space separated integers k (1≤k≤100000) and n (1≤n≤100000), denoting the size of the
tournament pool and the number of years for which you have been
supplied sufficient information.
Next is a single line describing Karl-Älgtav, containing the two
integers y (2011≤y≤2011+n−1) and p (0≤p≤2^31−1). These are his year of
entry into the tournament and his strength, respectively.
Then follow n+k−2 lines describing each of the other moose, in the
same format as for Karl-Älgtav.
Note that exactly k of the moose will have 2011 as their year of
entry, and that the remaining n−1 moose will have unique years of
entry.
You may assume that the strength of each moose is unique.
Output The year Karl-Älgtav wins the tournament, or unknown if the given data is insufficient for determining this.
Sample Input 1
2 4
2013 2
2011 1
2011 3
2014 4
2012 6
Sample Output 1
2013
Sample Input 2
2 4
2011 1
2013 2
2012 4
2011 5
2014 3
Sample Output 2
unknown
我的逻辑:
把所有的驼鹿都拿来,然后按强度对它们进行分类。然后从那里按年进行模拟,从所有驼鹿的列表中删除每年的获胜者,如果 Karl-Älgtav 是获胜者,则跳出循环。如果循环完成,我们还没有爆发,我们不知道他什么时候会赢所以我们打印'unknown'
我的代码:
line = input().strip().split()
k, n = int(line[0]), int(line[1])
line = input().strip().split()
m = (int(line[0]), int(line[1]))
c = [None for i in range(n+k-1)]
for i in range(n+k-2):
line = input().strip().split()
c[i] = ((int(line[0]), int(line[1])))
c[-1] = m
c.sort(key = lambda i:i[1])
year = 2011
won = False
for i in range(n):
yc = [y for y in c if y[0] <= year]
w = yc[-1]
c.remove(w)
if w == m:
print(year)
won = True
break
year += 1
if not won:
print('unknown')
我正在尝试加快速度但失败了。其他人能弄清楚吗?我最近还注意到,对于大多数竞争性编程问题,如果你不能在 Python 中暴力解决它,你可以在 Java 或 C++ 中解决。对于竞争性编程,是否建议我花更多时间学习那些语言或学习更好地优化 Python?
我用字典和堆尝试了不同的方法,但仍然没有达到时间限制。不过,它进一步得到了一个测试用例
代码:
from heapq import heappop, heappush, heapify
line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = {karl[1] : karl[0]}
for i in range(N+K-2):
line = input().strip().split()
moosen[int(line[1])] = (int(line[0]))
heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
mc = moosen.copy()
for k,v in moosen.items():
if v <= year:
heappush(heap, -k)
mc.pop(k)
moosen = mc.copy()
if -heappop(heap) == karl[1]:
won = True
print(year)
break
if not won:
print('unknown')
所以基本上我修改了我的第二种方法(见问题),使键和值颠倒,这使得字典搜索更快!
代码:
from heapq import heappop, heappush, heapify
from collections import defaultdict
line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = defaultdict(list)
for i in range(N+K-2):
line = input().strip().split()
moosen[int(line[0])].append(int(line[1]))
moosen[karl[0]].append(karl[1])
heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
for i in moosen[year]:
heappush(heap, -i)
if -heappop(heap) == karl[1]:
won = True
print(year)
break
if not won:
print('unknown')
我再次尝试解决一个问题来为即将到来的 USACO 比赛练习,但我无法满足 1 秒的时间限制:https://open.kattis.com/contests/v4xrif/problems/knigsoftheforest
All moose are knigs of the forest, but your latest moose-friend, Karl-Älgtav, is more interesting than most. In part because of his fondness of fermented blueberries, and in part because of the tribe he lives in. Each year his tribe holds a tournament to determine that year’s alpha-moose. The winner gets to lead the tribe for a year, and then permanently leaves the tribe. The pool of contenders stays constant over the years, apart from the old alpha-moose being replaced by a newcomer in each tournament.
Karl-Älgtav has recently begun to wonder when it will be his turn to win, and has asked you to help him determine this. He has supplied a list of the strength of each of the other moose in his tribe that will compete during the next n−1 years, along with their time of entry into the tournament. Assuming that the winner each year is the moose with greatest strength, determine when Karl-Älgtav becomes the alpha-moose.
Input The first line of input contains two space separated integers k (1≤k≤100000) and n (1≤n≤100000), denoting the size of the tournament pool and the number of years for which you have been supplied sufficient information.
Next is a single line describing Karl-Älgtav, containing the two integers y (2011≤y≤2011+n−1) and p (0≤p≤2^31−1). These are his year of entry into the tournament and his strength, respectively.
Then follow n+k−2 lines describing each of the other moose, in the same format as for Karl-Älgtav.
Note that exactly k of the moose will have 2011 as their year of entry, and that the remaining n−1 moose will have unique years of entry.
You may assume that the strength of each moose is unique.
Output The year Karl-Älgtav wins the tournament, or unknown if the given data is insufficient for determining this.
Sample Input 1
2 4 2013 2 2011 1 2011 3 2014 4 2012 6
Sample Output 1
2013
Sample Input 2
2 4 2011 1 2013 2 2012 4 2011 5 2014 3
Sample Output 2
unknown
我的逻辑: 把所有的驼鹿都拿来,然后按强度对它们进行分类。然后从那里按年进行模拟,从所有驼鹿的列表中删除每年的获胜者,如果 Karl-Älgtav 是获胜者,则跳出循环。如果循环完成,我们还没有爆发,我们不知道他什么时候会赢所以我们打印'unknown'
我的代码:
line = input().strip().split()
k, n = int(line[0]), int(line[1])
line = input().strip().split()
m = (int(line[0]), int(line[1]))
c = [None for i in range(n+k-1)]
for i in range(n+k-2):
line = input().strip().split()
c[i] = ((int(line[0]), int(line[1])))
c[-1] = m
c.sort(key = lambda i:i[1])
year = 2011
won = False
for i in range(n):
yc = [y for y in c if y[0] <= year]
w = yc[-1]
c.remove(w)
if w == m:
print(year)
won = True
break
year += 1
if not won:
print('unknown')
我正在尝试加快速度但失败了。其他人能弄清楚吗?我最近还注意到,对于大多数竞争性编程问题,如果你不能在 Python 中暴力解决它,你可以在 Java 或 C++ 中解决。对于竞争性编程,是否建议我花更多时间学习那些语言或学习更好地优化 Python?
我用字典和堆尝试了不同的方法,但仍然没有达到时间限制。不过,它进一步得到了一个测试用例
代码:
from heapq import heappop, heappush, heapify
line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = {karl[1] : karl[0]}
for i in range(N+K-2):
line = input().strip().split()
moosen[int(line[1])] = (int(line[0]))
heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
mc = moosen.copy()
for k,v in moosen.items():
if v <= year:
heappush(heap, -k)
mc.pop(k)
moosen = mc.copy()
if -heappop(heap) == karl[1]:
won = True
print(year)
break
if not won:
print('unknown')
所以基本上我修改了我的第二种方法(见问题),使键和值颠倒,这使得字典搜索更快! 代码:
from heapq import heappop, heappush, heapify
from collections import defaultdict
line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = defaultdict(list)
for i in range(N+K-2):
line = input().strip().split()
moosen[int(line[0])].append(int(line[1]))
moosen[karl[0]].append(karl[1])
heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
for i in moosen[year]:
heappush(heap, -i)
if -heappop(heap) == karl[1]:
won = True
print(year)
break
if not won:
print('unknown')