1

我在Codechef做一些练习题。有一个称为歧义排列的问题：

我对此的解决方案是：

while 1:
   cnt = int(raw_input())
   if cnt == 0:
      break
  vals = [int(u) for u in raw_input().split(' ')]
  valr = []
  for i in range(cnt):
    valr.append(vals.index(i+1)+1)
  if vals == valr:
    print 'ambiguous'
  else:
    print 'not ambiguous'

当我在Trypython.org中检查它时，它按预期工作。但是当我在 Codechef 中提交解决方案时，它超时了。

我的问题是这个。代码有什么问题（/可以改进），还是有什么特定的方法来处理测试机器的 sysin 和输出？

[编辑] 接受的解决方案提供了一些很好的建议，我重新考虑了代码逻辑并相应地修改了代码。代码现在可以在一段时间内运行，尽管它因错误答案而失败（尽管无法在我的测试用例中复制错误答案）。感谢您的建议。

import sys
def ambigcheck(lis):
   amb = 'ambiguous'
   for i in range(1,len(lis)+1):
       if lis[lis[i-1]-1] != i:
          amb = 'not ambiguous'
          break
   return amb 
while 1:
   cnt = int(sys.stdin.readline())
   if cnt == 0:
       break
   vals = [int(u) for u in sys.stdin.readline().split(' ')]
   sys.stdout.write(ambigcheck(vals))
4

1 回答 1

4

不要使用raw_input. 使用sys.stdin: 作为迭代器，或者read()它一次。并使用sys.stdout.write而不是print. 尝试只使用一次：预先计算整个输出并在之后将其写入屏幕。

这将为您提供 Python 中最快的 I/O。

更多提示：

  • 你不需要构造一个新的排列，你可以检查原始排列中的元素是否有正确的索引
  • 你不需要做全面检查，如果至少一个元素没有正确的索引，排列不是模棱两可的
  • 避免.index()方法，按索引检查，而不是按值检查
  • 您可以通过仅读取奇数行来更有效地处理输入itertools.islice（您不需要 Python 中的项目数）
于 2012-05-31T07:05:03.990 回答