对于任意一个h,只要它高度降到了与前一个高度下降过程中的公共值那么它就不需要花费代价继续下降。
如果它降得的当前高度与前一个高度没有公共值,则需要多花费一个代价,来降低自己的高度我们只需要开两个数组暴力做一下就行。
每个值下降次数很少的,可以用一个数组存储前一个数下降到1的中间数。
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
int h[200005],b[10005],ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> h[i];
while(h[1]>1){
b[++t]=h[1];
ans++;
h[1]=sqrtl(h[1]/2+1);
}
for(int i=2;i<=n;i++){
int v=h[i];
while(v>1){
int flag=0;
for(int j=1;j<=t;j++){
if(b[j]==v){
flag=1;
break;
}
}
if(flag==1) break;
ans++;
v=sqrtl(v/2+1);
}
t=0;
while(h[i]>1){
b[++t]=h[i];
h[i]=sqrtl(h[i]/2+1);
}
}
cout << ans;
return 0;
}