0

我正在尝试用 Python 解决这个问题，它的 CPU 时间限制为 1 秒，内存限制为 1024 兆字节：https ://open.kattis.com/contests/v4xrif/problems/grandpabernie

多年来，伯尼爷爷走遍了世界各地。他不再旅行那么多，但他喜欢告诉他的孙子们所有这些旅行的故事。他会告诉他们他第一次去以色列，或者第三次去希腊时的故事。

他的记忆以一种有趣的方式运作。他可以很容易地记住他第 k 次到某个特定国家的旅行，但他很难记住他是哪一年去的那次旅行。鉴于伯尼爷爷的所有旅行清单，您能否回答一些询问，询问他在哪一年第 k 次前往某个特定国家？

输入输入包括：

一行有一个整数n（1≤n≤100000），伯尼爷爷的行程次数；

n 行，每行包含一个国家的名称 s (1≤|s|≤20) 和一个整数 y (1≤y≤1000000)，表示伯尼爷爷在 y 年到 s 国家的旅行；

一行一整数q（1≤q≤100000），查询次数；

q 行，每行包含一个国家的名称 s 和一个整数 k，表示第 k 次伯尼爷爷去国家 s 的查询。

每个国家/地区名称仅由英文字母表中的字母组成。还保证，对于要求第 k 次前往国家 s 的每个查询，k 至少为 1，并且不大于伯尼爷爷前往国家 s 的次数。特别是，保证伯尼爷爷至少访问过一次国家。

输出 对于伯尼爷爷第 k 次旅行到国家 s 的每个查询，输出一行包含伯尼爷爷那次旅行的年份。

样本输入 1

4
Iceland 2016
Sweden 2015
Iceland 1982
Norway 1999
3
Sweden 1
Iceland 1
Iceland 2

样本输出 1

2015
1982
2016

样本输入 2

4
Iceland 2014
Iceland 2015
Iceland 2015
Iceland 2016
4
Iceland 4
Iceland 3
Iceland 2
Iceland 1

样本输出 2

2016
2015
2015
2014

我解决这个问题的策略是创建一个字典/哈希图，以国家名称作为键，并将他到该国的日期作为值列表。然后，我将遍历每个查询并从与查询对应的字典/哈希图中获取值。

我的代码：

dates = {}
for i in range(int(input().strip())):
    line = input().strip().split()
    city = line[0]
    year = int(line[1])
    if city in dates:
        dates[city].append(year)
    else:
        dates[city] = [year]

for i in range(int(input().strip())):
    line = input().strip().split()
    print(sorted(dates[line[0]])[int(line[1])-1])

可以看到，这是一个比较短的程序，但是速度还不够快。有没有办法加快速度？

4

1 回答 1

2

程序中最慢的部分将是每次查询时重复排序。

为了加快速度-

from collections import defaultdict

trips = defaultdict(list)

num_trips = int(input())
for _ in range(num_trips):
    destination, year = input().strip().split()
    trips[destination].append(year)

for years in trips.values():
    years.sort()

num_queries = int(input())
for _ in range(num_queries):
    destination, occurance = input().strip().split()
    year = trips[destination][int(occurance)-1]
    print(year)

此外，您可以延迟对年份进行排序，直到该国家/地区的查询到达，并保留已排序的国家/地区列表，但是除非您有一个输入可以在一个国家/地区为您提供大量条目，然后从不查询该国家/地区，您不会看到加速。

如果您知道查询列表不会太长，您还可以对其进行预处理以预先找出需要排序的唯一国家/地区集合，但事实并非如此，导致您超出了内存限制。

于 2021-09-25T17:43:51.200 回答