题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

定义$f(x,y)=(x \lor y)-y$，其中$\lor$表示按位或运算。

定义：

$b[2]=f(a[1],a[2])$

$b[3]=f(b[2],a[3])$

…

$b[n]=f(b[n-1],a[n])$

请你重新排列$a$，最大化$b[n]$的值。输出重新排列后的$a$。多解输出任意一解。

输入样例$1$

4
4 0 11 6

输出样例$1$

11 6 4 0

输入样例$2$

1
13

输出样例$2$

13

算法

按位贪心

挺怕这种题的，刚开始以为确定某种排序规则就好，但一直没想出来。这样的位运算求最值的思路最终还是要回归到按位贪心上。

分析函数的性质后发现$f(x,y)$其实就是从$x$中剥离掉$y$中的二进制位，比如$f(11,7)=8$，$11$的二进制是1011，$7$的二进制是111，$8$的二进制是1000，只要$11$中的$1$在$7$中也有，就会被剥离掉。

既然如此，那只要第一个数确定了，后面的数就是在剥离它二进制位中的$1$，顺序是无所谓的。但我们不能无脑把最大的那个数直接放到前面，因为可能有不止一个数在它的最高位是$1$，这个$1$会被那些数给消成$0$。因此，我们只需要把最大的满足最高位的那个$1$在其他所有数的相同位都是$0$的那个数放在第一个就可以了。

复杂度分析

时间复杂度

根据题目的$a[i]$范围，遍历$j \in [0,31]$位就可以覆盖，而每个位都要遍历$a[i],i \in [1,n]$，确定第$j$位的$1$是不是唯一的，时间复杂度可以近似为$O(n)$。

空间复杂度

仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 31; i >= 0; i--) {
        int cnt = 0, pos = 0;
        for(int j = 1; j <= n; j++) {
            if(a[j]>>i&1) {
                cnt++;
                pos = j;
            }
        }
        if(cnt == 1) {
            swap(a[1], a[pos]);
            break;
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}