我编写了一些代码来解决在线问题,这里.mustConstraint = set()notConstraint = set()violated = 0satisfied = 0 for i in range(0, int(input(''))): constrain = input('')
我已经编写了一些代码来解决在线问题, 这里 .
mustConstraint = set()
notConstraint = set()
violated = 0
satisfied = 0
for i in range(0, int(input(''))):
constraint = input('')
mustConstraint.add(frozenset(constraint.split()))
for i in range(0, int(input(''))):
constraint = input('')
notConstraint.add(frozenset(constraint.split()))
for i in range(0, int(input(''))):
group = input('')
group = set(group.split())
for x in mustConstraint:
if x & group == x:
satisfied +=1
for y in notConstraint:
if y & group == y:
violated += 1
violated += len(mustConstraint) - satisfied
print(violated)
总结一下这个问题,输入的第一行包含一个正整数 X,X => 0。接下来的 X 行输入将包含两个单词,以空格分隔。这两个单词 必须 属于同一组。输入的下一行将包含另一个正整数 Y,Y => 0。接下来的 Y 行输入将包含两个单词,以空格分隔。这两个单词 不能 属于同一组。输入的下一行将包含一个正整数 G,G >= 1。接下来的 G 行输入将分别包含三个不同的单词,以单个空格分隔。这三个单词被放在同一组中。
输出 0 到 X+Y 之间的一个整数,表示违反的约束的数量。
此处的 问题站点 ,因为通过提供的示例案例及其解释,可以更容易地理解问题。
不幸的是,由于最后一批有大约 300,000 个输入,我的嵌套 for 循环太慢了,无法满足 4 秒的时间限制——有人可以帮我优化代码吗?
大部分延迟来自于这个块:
for i in range(0, int(input(''))):
group = input('')
group = set(group.split())
for x in mustConstraint:
if x & group == x:
satisfied +=1
for y in notConstraint:
if y & group == y:
violated += 1
嵌套的 for 循环每次执行 100,000^2 次迭代,总计该代码块进行 200 亿次迭代(2*100,000^2)
如果有人能找到减少迭代次数的方法,那么将会产生很大的不同。