洛谷P1161 开灯题python

Question

洛谷P1161 开灯题python

题目描述

在一条无限长的路上，有一排无限长的路灯，编号为 $1,2,3,4,\dots$。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，$a,t$（$a$ 为实数，$t$ 为正整数）。将编号为 $\lfloor a\rfloor,\lfloor 2 \times a\rfloor,\lfloor3 \times a\rfloor,\dots,\lfloor t \times a\rfloor$ 的灯的开关各按一次。其中 $\lfloor k \rfloor$ 表示实数 $k$ 的整数部分。

在小明进行了 $n$ 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的 $n$ 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

输入格式

第一行一个正整数 $n$，表示 $n$ 次操作。

接下来有 $n$ 行，每行两个数，$a_i,t_i$。其中 $a_i$ 是实数，小数点后一定有 $6$ 位，$t_i$ 是正整数。

输出格式

仅一个正整数，那盏开着的灯的编号。

样例 #1

样例输入 #1

3
1.618034 13
2.618034 7
1.000000 21

样例输出 #1

20

提示

---

我的代码为

n = int(input())
ls = []
for i in range(n):
    a, t = map(eval, input().split())
    for j in range(1, t+1):
        m = int(a*j)
        if m in ls:
            ls.remove(m)
        else:
            ls.append(m)
print(ls[0])

但是运行有三个超时

请问如何减小时间复杂度

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

这个问题可以通过数学方法进行优化，而不是直接模拟每次操作。根据题目描述，当某个灯被操作了偶数次时，它会保持关闭状态；当被操作了奇数次时，它会变为开启状态。所以我们只需要统计每盏灯被操作的总次数，并找出被操作了奇数次的灯的编号即可。
具体来说，我们可以使用一个字典（或者哈希表）来记录每个编号灯被操作的次数。每次操作时，我们遍历要操作的灯的编号，对于每个编号，将其出现的次数加1。最后，遍历这个字典，找出出现奇数次的编号即为所求。
以下是优化后的代码：
pythonCopy code

n = int(input())
operations = []
for i in range(n):
a, t = map(eval, input().split())
operations.append((a, t))
lights = {}
for a, t in operations:
for j in range(1, t+1):
m = int(a*j)
lights[m] = lights.get(m, 0) + 1
# 找出被操作了奇数次的灯的编号
result = [key for key, value in lights.items() if value % 2 == 1]
print(result[0])

这段代码使用字典 lights 记录每个灯被操作的次数，然后遍历字典找出被操作了奇数次的灯的编号，并输出该编号。这样做的时间复杂度为
$O(n \cdot t)$，其中 $n$ 是操作次数，$t$ 是每次操作的最大编号。相比之前的做法，这种方法减小了时间复杂度，应该能够满足题目要求。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订