用贪心
2026-11-15 16:41:55
发布于:江苏
10阅读
0回复
0点赞
按位与的性质:高位优先,高位为 1,数一定更大
我们从最高位(比如 30 位,足够 int 范围)往低位尝试:
- 现在已经拼出来一个答案
res - 尝试把当前这一位设成 1:
tmp = res | (1 << bit) - 统计数组里有多少个数
a[i] & tmp == tmp(也就是这个数包含我们已经选好的所有 1) - 如果数量 ≥ m:说明可以选这一位为 1,
res = tmp - 否则:这一位不能取 1,跳过
原理:按位与结果的每一位是 1,要求选中的 m 个数这一位全部是 1
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
int res = 0;
for(int bit = 30; bit >= 0; bit--)
{
int now = res | (1 << bit);
int cnt = 0;
for(int x : a)
{
if((x & now) == now)
{
cnt++;
}
}
if(cnt >= m)
{
res = now;
}
}
cout << res << endl;
return 0;
}
这里空空如也

有帮助,赞一个