【题解】HackerRank - Yet Another Minimax Problem

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/yet-another-minimax-problem

题意

给出 n 个整数，求一个排列使得相邻两数的异或值的最大值最小，输出该值。

题解

  • 如果有一位所有数都是 0 或 1，则异或之后这一位始终是 0。
  • 如果有一位既有 1 又有 0，我可以把 1 和 0 各自放在一起，但是会由一个交界处，交界处的异或值的该位为 1，其他位置是 0。
  • 问题就是找到所有数不完全相同的最高的那位，然后按那位是 0 或 1 分成两组，求两组分别取一个数是异或值最小。
  • 利用 Trie 求一个数与一堆数异或的最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int maxn = 3000 + 10;
int n, a[maxn], b[maxn], la, lb, m;
int trie[maxn * 20][2];
int sz = 1;

void add(int n) {
    int u = 0;
    FORD(i, m - 1, -1) {
        bool b = (1 << i) & n;
        if (!trie[u][b]) trie[u][b] = sz++;
        u = trie[u][b];
    }
}

int query(int n) {
    int u = 0, ret = 0;
    FORD(i, m - 1, -1) {
        bool b = (1 << i) & n;
        if (!trie[u][b]) {
            ret += (1 << i);
            b ^= 1;
        }
        u = trie[u][b];
    }
    return ret;
}

int main() {
    cin >> n;
    m = 0;
    LL p = -1, q = 0;
    FOR(i, 0, n) {
        cin >> a[i];
        p &= a[i];
        q |= a[i];
    }
    if (!(p ^ q)) { puts("0"); return 0; }
    m = 31 - __builtin_clz(p ^ q);
    FOR(i, 0, n) {
        if (a[i] & (1 << m)) a[la++] = a[i];
        else b[lb++] = a[i];
    }
    FOR(i, 0, la) add(a[i]);
    LL ans = 1E10;
    FOR(i, 0, lb) ans = min(ans, (LL)query(b[i]));
    cout << ans + (1 << m) << endl;
}