时间戳

首页 > 解决方案 > Python列表排序与仿真优化问题

python - Python列表排序与仿真优化问题

问题描述

我再次尝试解决即将到来的 USACO 比赛的练习问题，但无法满足 1 秒的时间限制：https ://open.kattis.com/contests/v4xrif/problems/knigsoftheforest

所有的驼鹿都是森林之王，但你最近的驼鹿朋友 Karl-Älgtav 比大多数人更有趣。部分是因为他喜欢发酵蓝莓，部分是因为他居住的部落。每年他的部落都会举办一场比赛来确定当年的阿尔法驼鹿。获胜者可以领导部落一年，然后永久离开部落。多年来，竞争者的数量保持不变，除了在每场比赛中老的 alpha-moose 都会被新人取代。

Karl-Älgtav 最近开始想知道什么时候会轮到他获胜，并要求您帮助他确定这一点。他提供了一份名单，列出了他部落中将在接下来的 n-1 年内参加比赛的每只驼鹿的实力，以及它们参加比赛的时间。假设每年的获胜者是最强壮的驼鹿，确定 Karl-Älgtav 何时成为阿尔法驼鹿。

输入 输入的第一行包含两个空格分隔的整数 k (1≤k≤100000) 和 n (1≤n≤100000)，表示锦标赛池的大小和为您提供了足够信息的年数。

接下来是描述 Karl-Älgtav 的单行代码，包含两个整数 y (2011≤y≤2011+n−1) 和 p (0≤p≤2^31−1)。这些分别是他进入锦标赛的年份和他的实力。

然后按照与 Karl-Älgtav 相同的格式，按照 n+k-2 行描述其他每只驼鹿。

请注意，恰好有 k 头驼鹿将 2011 年作为它们的进入年份，而剩余的 n-1 头驼鹿将具有唯一的进入年份。

你可以假设每只驼鹿的力量都是独一无二的。

输出Karl-Älgtav 赢得比赛的年份，或者如果给定的数据不足以确定这一点，则未知。

样本输入 1

2 4
2013 2
2011 1
2011 3
2014 4
2012 6

样本输出 1

2013

样本输入 2

2 4
2011 1
2013 2
2012 4
2011 5
2014 3

样本输出 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')

标签： pythonarrayslistoptimizationsimulation

解决方案

所以基本上我修改了我的第二种方法（见问题），以便键和值反转，这使得字典搜索更快！代码：

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')

推荐阅读