又一个极小问题 您将获得非负整数。我们将长度的某个排列 (( 的分数定义为最大值。
找到具有最小可能分数的排列并打印其分数。
注意：是独占 OR (XOR( 运算符。
法典：
# Enter your code here. Read input from STDIN. Print output to STDOUT
import itertools
import math
from operator import xor
def per_me(g):
max =0
for r in range(0,len(g)-1):
if(xor(g[r],g[r+1])>max):
max=(xor(g[r],g[r+1]))
return max
n = int(raw_input())
arr = raw_input()
l = list(map(int,arr.split(' ')))
p = itertools.permutations(l)
count = 1000000000000
for i in p:
if(per_me(i)<count):
count = per_me(i)
print count
输入：
10
12 0 4 3 1 1 12 3 11 11
输出：
8
如何减少此代码所需的时间
设i是最大的自然数，以便某些但不是全部输入数具有位i设置。最小分数将是a xor b的最小值，其中a设置了位i，b没有，并且输入列表中a和b。很容易看出，分数必须至少这么大(因为在任何排列中的某个点，必须有一个带有位i的数字，旁边必须有一个没有位i设置的数字(，以及任何排列，将所有输入分组，首先设置位i，然后设置没有位i输入，并将上面的a和b放在边界上完全达到该分数(因为a xor b将i作为其最高位，而所有其他相邻数字的最高位小于i(。
即使不进一步考虑，这也将问题简化为 O(n^2( 问题，这应该足够好，因为 n <= 3000。
def minxor(aa):
bits = unbits = 0
for a in aa:
bits |= a
unbits |= ~a
i = bits & unbits
while i & (i-1):
i &= i-1
xs = [a for a in aa if a & i]
ys = [a for a in aa if (a & i) == 0]
return min(x ^ y for x in xs for y in ys)
print minxor([1, 2, 3, 4])
print minxor([1, 2, 3])
print minxor([7, 6, 5, 4])
print minxor([12, 0, 4, 3, 1, 1, 12, 3, 11, 11])
(请注意，在代码中，i与描述中并不完全相同 - 而不是某些但不是所有输入中存在的最大位的索引，而是该位的值(。
在计算min时，可以通过不比较每个x和y来进一步优化。这将解决方案简化为 O(n log n(，即使对于相当大的输入列表也可以找到解决方案：
def bestpair(xs, ys, i):
if i == 0:
return 0
x0 = [x for x in xs if (x&i)==0]
x1 = [x for x in xs if x&i]
y0 = [y for y in ys if (y&i)==0]
y1 = [y for y in ys if y&i]
choices = []
if x0 and y0:
choices.append(bestpair(x0, y0, i//2))
if x1 and y1:
choices.append(bestpair(x1, y1, i//2))
if choices:
return min(choices)
return bestpair(xs, ys, i//2) + i
def minxor(aa):
bits = unbits = 0
for a in aa:
bits |= a
unbits |= ~a
i = bits & unbits
while i & (i-1):
i &= i-1
return bestpair([a for a in aa if a & i], [a for a in aa if (a & i)==0], i)
print minxor(range(100000))