思路:贪心

容易发现，从二进制的视角来看，只要每一个$bit$都变成一样即可。所以可以分别独立的考虑每一位的最小代价。那么对于每一个$bit$ , 我们要么将所有的$0$ 都变成 $1$ , 要么将所有的$1$ 都变成 $0$. 所以最小代价就是$0,1$ 中出现次数少的那个。

举个例子:

4

1 2 3 4

那么最小代价就是5，如下图所示

代码

C++代码

#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5 + 5;
#define ll long long 
// cnt[i][0] 代表这n个整数中，第i位分别出现了多少次0 
// cnt[i][1] 代表这n个整数中，第i位分别出现了多少次1 
ll cnt[40][2];
int main (){
    int n;
    cin >> n;
    for (int i = 1 ; i <= n; i++){
		ll x;
		cin >> x;
        // 统计x
		for (int j = 0 ; j < 34 ; j++){
			int v = (x >> j) & 1;
			cnt[j][v]++;
		}
    }
    // 按二进制的每一位计算贡献
    int ans = 0;
    for (int i = 0 ; i < 34 ; i++){
        // 看最小出现次数。
    	ans += min(cnt[i][0] , cnt[i][1]);
    }
    cout << ans << endl;
    return 0;
}

题目内容

曾经有一个名叫小红的年轻程序员，他梦想成为一名优秀的算法工程师。一天，他遇到了这样一个问题：给定一个由 $n$ 个非负整数组成的数组，他每次可以选择其中一个数的二进制表示中的某一位进行取反操作，问他最少需要多少次操作才能使得这个数组中的所有数相等。

小红日思夜想也没有想出来怎么解决这个问题，于是，他决定请教你这个问题，希望你能够提供一个更加高效的算法，以便让他能够早日实现自己的梦想。

输入描述

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个非负整数 $a_i$ ，代表数组的元素。

$1\le n \le 10^5$ ， $0 \le a_i \le 2^{31} -1$

输出描述

一个整数，代表最小的操作次数。

样例

输入

5
3 5 1 4 8

输出

6