C. Amr and Chemistry
题意
给出一个长度为n<1e5的数组
一次操作能让ai变为2ai 或 让ai变为 ai/2 下取整
问最少几次能让全部的数组元素相等
题解
对一个数 ×2或÷2下取整
用二进制表示相当于位运算中<<1或>>1
观察发现 右移或左移不能产生新的二进制1
但能删去原来二进制中的1
所以要操作最小次数得到相同元素必然会是数组a中所有数的二进制串
中最长的相同前缀
比如3 5 6的二进制：
011
101
110
为了找最长的相同前缀 我们需要将首位的一移动到相同的位置
变为
110
101
110
所以3 5 6 的最长相同前缀为 100
我们得到了这个前缀 对于这个前缀我们不关心有几个0
因为可以通过左移右移得到
我们需要操作将所有数的二进制删去多余的1调整0的个数
获得与最长前缀相同的值 (即最后所有数都相等)
所以在得到最长相同前缀后 逐个枚举
num=001 ，010，100
统计所有数变为num需要的操作次数更新答案
其他方法
将所有数a[i]通过 ×2 or /2得到的数所需要的操作次数num[x]统计出来
即num[a[i]×2]=num[a[i]]+1 或num[a[i]/2]=num[a[i]]+1
num[a[i]×4]=num[a[i]×2]+1 ….
同时记录有多少个数ai可以通过操作变为x记为cnt[x]
然后枚举最后数组所有数的最终值 x
若cnt[x]==n 则可能通过操作得到 更新答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
int ndata[Max],data[Max];
int main() {
int n;cin>>n;
int maxn=0;
for(int i=0;i<n;i++){
cin>>data[i];ndata[i]=data[i];
maxn=max(maxn,data[i]);
}
int cnt=0;
while(maxn){
maxn>>=1;
cnt++;
}
maxn=1<<(cnt-1);
for(int i=0;i<n;i++){
while(ndata[i]<maxn)ndata[i]<<=1;
}
int temp=ndata[0];
for(int i=1;i<n;i++)temp&=ndata[i];
maxn=temp;
while(temp){
if(temp&1)break;
temp>>=1;
}
int ans=1e9,fn=-1;
for(int bios=0;(temp<<bios)<=maxn;bios++){
int need=0,num=temp<<bios;
for(int i=0;i<n;i++){
int now=data[i];
int diff=ndata[i]^maxn;
if(diff){
int biosnow=ndata[i];
while(now>biosnow)biosnow<<=1,diff<<=1;
while(now<biosnow)biosnow>>=1,diff>>=1;
while(diff){
now>>=1;
diff>>=1;
need++;
}
}
while(now>num){
now>>=1;
need++;
}
while(now<num){
now<<=1;
need++;
}
}
ans=min(ans,need);
}
cout<<ans<<endl;
}
|