如果没有相邻元素的差为1，则整数1,2，…，n的排列被称为漂亮。 />给出n，如果存在这样的排列，就构造一个漂亮的排列
约束非常严格：
时间限制：1.00 s
<内存限制：512 MB
1≤n≤10 ^ 6
代码如下：
n = int(input())
if n == 2 or n == 3:
print("NO SOLUTION")
elif n == 1:
print(1)
elif n == 4:
print("3 1 4 2")
else:
for i in range(1, n + 1, 2):
print(str(i) + " ", end=" ")
for i in range(2, n + 1, 2):
print(str(i) + " ", end=" ")
它通过了所有测试，但n = 1000000除外。对于该测试，需要15秒。在我的机器上。代码在Python 3.8中。
问题是，在打印数字方面可以改进什么？
#1 楼
不错的解决方案，几乎没有建议：逐个打印数字可能是个问题。首先生成数字列表，然后只调用一次
print。已经处理过
n==1的情况，因此可以删除第一个elif。应用建议：
n = int(input())
if n == 2 or n == 3:
print("NO SOLUTION")
elif n == 4:
print("3 1 4 2")
else:
beautiful_perm = [*range(1, n + 1, 2), *range(2, n + 1, 2)]
print(' '.join(map(str, beautiful_perm)))
通过反转范围，我们不需要检查
n==4：n = int(input())
if n == 2 or n == 3:
print("NO SOLUTION")
else:
beautiful_perm = [*range(2, n + 1, 2), *range(1, n + 1, 2)]
print(' '.join(map(str, beautiful_perm)))
CSES上的运行时：
n = 906819 (CPython3)
Original: 0.92 s
Improved: 0.26 s
n = 1000000 (CPython3)
Original: timeout
Improved: 0.28 s
n = 1000000 (PyPy3)
Original: 0.61 s
Improved: 0.15 s
评论
\ $ \ begingroup \ $
print（''.join（map（str，range（2，n + 1，2））），''.join（map（str，range（1，n + 1，2）））））效率更高。
\ $ \ endgroup \ $
– GZ0
20-11-15在11:40
\ $ \ begingroup \ $
我什至还要补充一点，他们告诉我们内存限制为512Mb，这暗示着您不应该一张一张地打印所有内容。
\ $ \ endgroup \ $
–沃尔夫特
20 Nov 16'9:18
\ $ \ begingroup \ $
@Walfrat也许我缺少了一些东西。 512MB的内存限制如何阻止您一一打印所有内容？
\ $ \ endgroup \ $
–碎石机
20 Nov 16 '14：06
\ $ \ begingroup \ $
没什么，但是如果它是52Kb，则一次打印所有内容都会遇到问题。由于您有足够的内存，因此更有可能在打印之前先构建完整的解决方案。
\ $ \ endgroup \ $
–沃尔夫特
20 Nov 16 '14：51
\ $ \ begingroup \ $
如果您计算机上的解决方案从0.61降到0.15，您如何期望OP从15.0降到1.0？
\ $ \ endgroup \ $
–托马斯·韦勒（Thomas Weller）
20-11-16在19:15
#2 楼
您的代码被原样接受。只需选择PyPy3而不是CPython3。另一个版本也被CPython3接受（使用Marc的逻辑，但使用一种更简单的打印方式）：
n = int(input())
if 2 <= n <= 3:
print("NO SOLUTION")
else:
print(*range(2, n + 1, 2), *range(1, n + 1, 2))
这样的打印将循环从您的自己的Python循环，其中有许多
print调用到一个调用并在C中循环。不过，使用Marc的' '.join更快。测试案例＃20的时间，其中n = 906819，这是您的最大案例，其速度足够快而不会被杀死： CPython3 PyPy3
Yours 0.93 s 0.56 s
Mine 0.37 s 0.32 s
Marc's 0.25 s 0.14 s
为什么Marc的方法更快？
print文档说：“文件参数必须是带有write(string)方法的对象”。如果我们使用自己的对象，那么在Marc中的写调用将比在我的对象中少得多：class Write:
def write(self, string):
print(f'write({string!r})')
nums = range(5)
print(' '.join(map(str, nums)), file=Write())
print()
print(*nums, file=Write())
输出：
write('0 1 2 3 4')
write('\n')
write('0')
write(' ')
write('1')
write(' ')
write('2')
write(' ')
write('3')
write(' ')
write('4')
write('\n')
所有这些函数调用的开销是可能是让我的速度变慢的原因。
' '.join(...的开销似乎更小。话说，如果速度足够快，我通常会选择我的方式，因此请先尝试一下。除非在比赛中，我有理由相信它可能不够快，否则提交失败将受到处罚。
评论
\ $ \ begingroup \ $
+1为紧凑代码。如果我在CSES上运行它（PyPy3 n = 100000），它的运行时间为0.34 s，比我的慢2倍。你知道为什么吗？还是CSES不可靠？
\ $ \ endgroup \ $
– Marc
20 Nov 14 '13：00
\ $ \ begingroup \ $
@Marc我想说它实际上慢了大约三倍。最小时间（对于像n = 1的小n）为0.05 s。如果减去这些开销，您的开销为0.10 s，我的开销为0.29 s。在我看来，CSES确实是“可靠的”，从某种意义上说，重复提交相同的代码会重复给我相同的时间，并且开销相对较小（例如，与LeetCode不同，因为相同代码的时间变化很大，开销可能是超过报告时间的99％）。从经验（使用CPython）来看，我希望自己的方法会比较慢，但只要速度足够快，我便更喜欢它以简化操作。
\ $ \ endgroup \ $
–极好的雨
20-11-14在13:17
\ $ \ begingroup \ $
@Marc Btw与CPython3，差别较小。我的n = 1 = 0.02 s，n = 1e6 = 0.44 s，因此0.42 s没有开销。对于您而言，这是0.02 s和0.28 s，因此0.26 s（无开销）。因此，您的速度是那里的1.6倍。
\ $ \ endgroup \ $
–极好的雨
20-11-14在13:45
\ $ \ begingroup \ $
非常感谢您的解释！它本来可以是一个评论；）
\ $ \ endgroup \ $
– Marc
20-11-14在14:06
\ $ \ begingroup \ $
@Marc是的，您是对的，尤其是因为问题的标题和最后一段都明确地说明了打印问题。现在在我的答案中添加了内容。
\ $ \ endgroup \ $
–极好的雨
20-11-14在14:59
评论
这不取决于终端的速度吗？@Matt，是的。只需添加即可在CPython上执行