感受

思路






#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int tr[maxn * 32][2], cnt;
int L[maxn * 32], R[maxn * 32];
int n;
int a[maxn];
void add(int x, int rk){
    int cur = 0;
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1;
        if(!tr[cur][f]) tr[cur][f] = ++cnt;
        if(!L[cur]) L[cur] = rk;
        else L[cur] = min(L[cur], rk);
        R[cur] = max(R[cur], rk);
        cur = tr[cur][f];
    }
}
ll query(int cur, int x, int i){
    ll ans = 0;
    for(; i >= 0; i--){
        int f = (x >> i) & 1;
        if(!tr[cur][f]) ans += 1 << i, f ^= 1;
        cur = tr[cur][f];
    }
    return ans;
}
ll ans;
void dfs(int cur, int dep){
    if(tr[cur][0]) dfs(tr[cur][0], dep - 1);
    if(tr[cur][1]) dfs(tr[cur][1], dep - 1);
    if(tr[cur][0] && tr[cur][1]){
        int son = tr[cur][0]; ll tmp = -1;
        for(int i = L[son]; i <= R[son]; i++){
            ll c = (1 << (dep - 1)) + query(tr[cur][1], a[i], dep - 2);
            if(tmp == -1) tmp = c;
            else tmp = min(tmp, c);
        }
        ans += tmp;
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        add(a[i], i);
    }
    dfs(0, 31);
    printf("%lld\n", ans);
    return 0;
}