题解 | #游游的除2操作#

#include <iostream>

#include <algorithm>
#include <string>

using namespace std;
//我的算法复杂度是O(nlogn) 不会超时哦。如有更好的方法欢迎留言 让我学习一下
//本题思路是先将数组排序一下(可排可不排)其次将数组中每个数都转化成二进制的0,1串保存到字符串数组中
//然后再查找字符串数组中有多少个相同的前缀，最后用每个字符串减去相同前缀个数再相加就得出结果了
//例：n=4 数组分别为6  37   110   298  化成二进制分别为110  100101  1101110   1000101010
//我们发现相同的前缀只有一个就是开头的1 然后每个字符串长度都减一再相加就是答案啦
int n,a[100010];
string s[100010];
void solve(){
    int m,j,ans=0;
    string s2=s[0];
    for(int i=1;i<s[1].size();i++){
        for(j=1;j<n;j++){
        string s1=s[j];
        if(s1[i]!=s2[i]) break;
      }
      if(j!=n) {m=i;break;}
    }
    for(int i=0;i<n;i++){
        ans+=s[i].size()-m;
    }
    cout << ans ;
}
void ejz(){
    for(int i=0;i<n;i++){
        int m=a[i];
        string s1;
        while(m){
		  //利用辗转相除法将整数数组转化为二进制
            s1+=char(m%2+'0');
            m/=2;
        }
        reverse(s1.begin(),s1.end());
	  //辗转相除法转化为二进制最高位和最低为是反的，所以还要利用reverse函数将该字符串反转
        s[i]=s1;
    }
}
int main() {
    cin >> n ;
    for(int i=0;i<n;i++)
    cin >> a[i] ;
    sort(a,a+n);
    ejz();//将数组全部转化成二进制的0 1 串
    solve();
}