烹饪问题 题解

题目分析

本题给出 $N$ 个整数 $a_1 \sim a_N$，要求从这些数中选出两个数，使得它们的按位与结果最大，输出这个最大的按位与值。
$N$ 的范围高达 $10^6$，$a_i$ 在 int 范围内（最大 $2^{31}-1$），因此直接枚举所有数对会达到 $O(N^2)$ 级别，显然不可行。

我们需要利用按位与的性质和数字位数的有限性，设计更高效的算法。

解题思路

要想使两个数的按位与结果尽可能大，应该尽可能让高位为 1。
这是因为在二进制中，高位的影响远远大于所有低位之和（例如 $1000_2 = 8$ 而 $0111_2 = 7$）。

因此可以采用贪心策略：从最高位（第 31 位）到最低位（第 0 位）依次判断，当前位是否能在最终答案中为 1。

具体做法是维护一个候选集合 $S$（初始为全部 $N$ 个数），表示可能产生最优答案的两个数所在的集合。对于当前二进制位 $k$（从高到低）：

• 检查 $S$ 中有多少个数在第 $k$ 位上是 1；
• 如果这样的数不少于 2 个，说明我们可以选出两个数，使它们在这一位同时为 1（且高位已经满足之前的条件）。此时将答案的第 $k$ 位置为 1，并将 $S$ 缩小为这些第 $k$ 位为 1 的数（因为最终选出的两个数必然来自这个子集）；
• 如果这样的数少于 2 个，则答案的第 $k$ 位只能为 0，候选集合 $S$ 保持不变（仍然在原来的集合中寻找更低位的机会）。

处理完所有二进制位后，答案就自然得到了。由于我们始终在维护的候选集合中挑选，贪心选择的高位一定是最优的。

算法说明

上述思路中，最关键的操作是：对候选集合 $S$，统计其中有多少个数的第 $k$ 位为 1，并将它们快速分离出来。
本题的 C++ 参考代码使用了一种巧妙的方法——原地分区，从而避免了创建额外的数组，并高效地维护候选集合。

分区函数 sort(l, r, k)

cpp
复制
1int sort(int l, int r, int k) {
2    while (l <= r) {
3        while ((l <= r) && ((a[l] >> k) & 1)) l++;
4        while ((l <= r) && (!((a[r] >> k) & 1))) r--;
5        if (l < r) swap(a[l++], a[r--]);
6    }
7    return r;
8}

这个函数的作用是：在数组 $a$ 的闭区间 $[l, r]$ 中，将所有第 $k$ 位为 1 的元素移动到左侧，第 $k$ 位为 0 的元素移动到右侧，并返回左侧部分（第 $k$ 位为 1）的最后一个下标。

算法使用了双指针：

• 左指针 l 向右移动，直到遇到一个第 $k$ 位为 0 的元素；
• 右指针 r 向左移动，直到遇到一个第 $k$ 位为 1 的元素；
• 若 l < r，交换这两个元素，然后继续移动。

最终 l > r，此时 r 指向左侧为 1 的最后一个元素。因此返回 r。

值得注意的是，这个分区函数并不会打乱候选集合的相对顺序对后续判断的影响，因为每一轮我们只关心指定位是否为 1，函数会完全按照当前位重新划分。

主算法流程

初始时，候选集合为整个数组 $a[1..n]$（注意数组下标从 1 开始）。

从最高位 i = 31 向下枚举到 0：

cpp
复制
1for (int i = 31; i >= 0; i--) {
2    if ((j = sort(1, n, i)) >= 2) {
3        ans = ans | (1 << i);
4        n = j;
5    }
6}

• 调用 sort(1, n, i) ，返回 j，表示当前候选集合（前 n 个元素）中，第 i 位为 1 的元素个数为 j（因为它们被移到了最前面，下标 $1 \sim j$）。
• 如果 j >= 2：
  • 说明可以选出两个数满足这一位为 1，因此将答案的第 i 位置为 1（ans |= 1 << i）；
  • 缩小候选集合为这些第 i 位为 1 的数，即令 n = j。
• 如果 j < 2（即 j 为 0 或 1）：
  • 无法选出两个数在这一位都为 1，答案这一位保持 0，候选集合不变（n 不变）。虽然经过分区后，少数的第 i 位为 1 的元素被移到了前面，但下一轮对更低位进行分区时，仍然会对整个候选集合 [1, n] 重新洗牌，因此不影响正确性。

处理完所有位后，ans 就是最大的按位与值。

时间复杂度分析

• 外层循环执行 32 次（第 31 位到第 0 位）。
• 每次循环中，分区操作 sort 仅扫描当前候选集合一次，复杂度为 $O(|S|)$。候选集合的大小从初始的 $N$ 逐渐缩小，最坏情况下每次都不缩小，总复杂度为 $O(32 \times N)$。
• 对于 $N \le 10^6$，$32 \times 10^6 \approx 3.2 \times 10^7$ 次基本操作，在 1 秒的时间限制和 256MB 内存下完全可以接受。

空间复杂度为 $O(N)$，用于存储数组 $a$。

参考代码

完整的 C++ 代码如下（基于题目所给参考代码，添加了注释便于理解）：

cpp
复制
1#include <cstdio>
2#include <iostream>
3#include <algorithm>
4#include <cstdlib>
5#include <string>
6using namespace std;
7
8const int MAX_N = int(1e6) + 100;
9int a[MAX_N];
10
11// 分区函数：将 a[l..r] 按第 k 位是否为 1 划分
12// 返回左侧部分（第 k 位为 1）的最后一个下标
13int sort(int l, int r, int k) {
14    while (l <= r) {
15        while ((l <= r) && ((a[l] >> k) & 1)) l++;      // 找左边第一个第k位为0的
16        while ((l <= r) && (!((a[r] >> k) & 1))) r--;    // 找右边第一个第k位为1的
17        if (l < r) swap(a[l++], a[r--]);                 // 交换
18    }
19    return r;  // r 是最后一个1的位置
20}
21
22int main() {
23    int n, j, ans = 0;
24    scanf("%d", &n);
25    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
26    
27    // 从高位到低位贪心
28    for (int i = 31; i >= 0; i--) {
29        // 在当前候选集合 a[1..n] 中划分
30        if ((j = sort(1, n, i)) >= 2) {
31            ans = ans | (1 << i);  // 这一位可以为1
32            n = j;                 // 缩小候选集合
33        }
34        // 否则 ans 该位保持 0，候选集合不变
35    }
36    
37    printf("%d\n", ans);
38    return 0;
39}

代码解释

• 第 4 行：定义数组最大长度，略大于 $10^6$。
• 第 9–17 行：sort 函数，通过双指针实现原地分区，是算法核心。
• 第 21 行：读入 $N$ 和所有食材的美味度 $a_i$。
• 第 24–30 行：主循环，从第 31 位降到第 0 位。j 接收分区后左侧（第 i 位为 1）的长度，若 j >= 2，则更新答案并收缩区间；否则不做操作，继续下一位。
• 第 32 行：输出最终答案。

拓展与总结

• 核心思想：按位贪心 + 维护候选集合。这种思想也常用于解决“最大异或对”等问题。
• 原地分区：巧妙利用双指针避免了额外空间，同时保证每次操作仅与当前候选集合大小有关。
• 适用性：本题数值范围固定（32 位整数），因此复杂度可控。若数据范围更大（例如 64 位），只需调整循环起始位即可。

希望这份题解能帮助大家理解并掌握这类“最大按位与”问题的通用解法。