当前位置：首页 > news >正文

【C++贪心位运算】B3930 烹饪问题|普及

news 2025/5/11 16:14:52

本文涉及知识点

C++贪心
位运算、状态压缩、枚举子集汇总

B3930 [GESP202312 五级] 烹饪问题

题目描述

有 $N$ 种食材，编号从 $0$ 至 $N - 1$ ，其中第 $i$ 种食材的美味度为 $a_i$ 。

不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为 $x$ 和 $y$ ，那么它们的契合度为 $x\ \text{and}\ y $。

其中， $\text{and}$ 运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足，再逐位进行与运算。例如， $12$ 与 $6$ 的二进制表示分别为 $1100$ 和 $0110$ ，将它们逐位进行与运算，得到 $0100$ ，转换为十进制得到 4，因此 $\text{and} 6 = 4$ 。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。

现在，请你找到契合度最高的两种食材，并输出它们的契合度。

输入格式

第一行一个整数 $N$ ，表示食材的种数。

接下来一行 $N$ 个用空格隔开的整数，依次为 $a_1,\cdots,a_N$ ，表示各种食材的美味度。

输出格式

输出一行一个整数，表示最高的契合度。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

样例 #2

样例输入 #2

5
5 6 2 10 13

样例输出 #2

提示

样例解释 1

可以编号为 $1, 2$ 的食材之间的契合度为 $2\ \text{and} \ 3=2$ ，是所有食材两两之间最高的契合度。

样例解释 2

可以编号为 $3, 4$ 的食材之间的契合度为 $10\ \text{and}\ 13=8$ ，是所有食材两两之间最高的契合度。

数据范围

对于 $40\%$ 的测试点，保证 $\le 1,000$ ；

对于所有测试点，保证 $\le 10^6$ ， $0\le a_i \le 2,147,483,647$ 。

贪心+试填法

int 共32位，去掉符合位，还是31位。从高到低处理第i位,i = 30 to 0。
如果第i位为1的数字达到2，则删除所有此位为0的数字。如果选择了这些数字，此位一定是0。
如果第i位为1的数字没有或只有一个，则什么都不干。
余下的任意两个数字位与，就是本题答案。
向量删除元素时间复杂度是O(n)，如果对顺序没有要求，和最后一个元素交换后删除，这样时间复杂度是：O(1)。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>#include <bitset>
using namespace std;class Solution {
public:int MaxS(vector<int>& nums) {for (int i = 30; i >= 0; i--) {vector<int> tmp;for (const auto& n : nums) {if (n & (1 << i)) { tmp.emplace_back(n); }}if (tmp.size() >= 2) { tmp.swap(nums); }}if (0 == nums.size()) { return 0; }return nums.front() & nums.back();}
};
int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint n;scanf("%d", &n);Solution slu;vector<int> nums;while (n--) {int h;	scanf("%d", &h);nums.emplace_back(h);		}int res = slu.MaxS(nums);printf("%d\r\n", res);return 0;
}

单元测试

	TEST_METHOD(TestMethod1){nums = { 1, 2, 3 };auto res = Solution().MaxS(nums);AssertEx(2, res);}TEST_METHOD(TestMethod11){nums = { 5, 6, 2 ,10 ,13 };auto res = Solution().MaxS(nums);AssertEx(8, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功