给定一个数组,每次模作可以选择数组的一个元素,将它的二进制的某一位取反(假定每个元素都是32位的非负整数,范国在[0,2^31-1])。请你用c++写一个程序,求出使得数组所有元素都相等的最小操作次数
时间: 2024-05-09 08:17:46 浏览: 132
可以通过统计数组中每个元素二进制位上的1的个数,找到操作后相等的二进制位数最小值,最终操作次数为所有数中该二进制位为1的个数之和。
以下是 C 语言代码实现:
```c
#include <stdio.h>
int countOne(int x) {
int count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int minOp = n * 32;
for (int i = 0; i < 32; i++) {
int totalOne = 0;
for (int j = 0; j < n; j++) {
totalOne += countOne(arr[j] ^ (1 << i));
}
minOp = totalOne < minOp ? totalOne : minOp;
}
printf("%d\n", minOp);
return 0;
}
```
输入样例:
```
5
3 4 6 9 12
```
输出样例:
```
3
```
解释:将第 0、2、3 三个二进制位取反,所有数变成了 2,共需要操作 3 次。
阅读全文