CodeForces - 1447E（分治）
90nwyn
2020-11-26 21:55:37
[题目链接](https://vjudge.net/problem/CodeForces-1447E)
------------
贪心地从高位到低位考虑
对于当前二进制第$i$位下，第$i$位为$1$的数有$c_1$个，为$0$的数有$c_0$个，若$max(c_1,c_0)>1$，显然最终无法构成一棵树，需要在两者之间选择一个，使其数量变为$1$，以此类推，分治递归求解
------------
```python
import math
def dfs(a):
if(len(a)==1):
return 1
k=1<<(int(math.log2(a[0]^a[-1])))
for i,p in enumerate(a):
if(p&k):
break
return 1+max(dfs(a[:i]),dfs(a[i:]))
n=int(input())
a=list(map(int,input().split()))
a.sort()
print(n-dfs(a))
```