Problem A. Chemistry

Input file: chemistry.in

Output file: chemistry.out

Time limit: 1 seconds

Memory limit: 256 megabytes

香香手中有n瓶化学药剂，每瓶化学药剂都有一个能量值ai。现在她想把这些药剂的能量值全部变成一样的，她有两台机器，其中一台机器一次可以把一瓶药剂的能量值翻倍，ai变成2ai，另一台机器一次可以把一瓶药剂的能量值变为一半，ai变成。

然而每台每次启动都需要单位1的能量，她所储存的能量不多了，请你帮她计算一下用最少的能量完成这个任务。

Input

第一行输入一个n（1 <= n <= 10^5 )

第二行输入n个数，用空格隔开，表示每瓶药剂的能量值ai

（1 <= ai <= 10^5）

Output

输出一行，表示最少需要的能量值是多少。

Sample test(s)

input

3

4 8 2

output

2

input

3

3 5 6

output

5

样例解释：

第一个样例能量值全部为成4 ，第二个样例全部变为1。

范围：

对于10% ， n = 2

对于30% ， n <= 100

对于另10% ， ai <= 1000

对于100% ， n <= 10^5 , ai <= 10^5

 

　　分析：

　　明显的DP，f[i][j]表示前i个数全部变成j所要耗费的能量，然后就是各种优化。。。。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 const int MAX=100005; 9 const int inf=0x3f3f3f3f; 10 int a[MAX]; 11 int b[MAX],b2[MAX]; 12 int c[10000000]; 13 int f[10][1000000]; 14 int may[1000000]; 15 int N; 16 int ANS=inf; 17 int MIN; 18 int main(){ 19 // freopen("chemistry.in","r",stdin); 20 // freopen("chemistry.out","w",stdout); 21 scanf("%d",&N); 22 for(int i=1;i<=N;i++) scanf("%d",&a[i]); 23 sort(a+1,a+N+1); 24 for(int i=1;i<=N;i++) b[i]=a[i],b2[i]=a[i]; 25 26 for(int i=1;i<=N;i++){ //筛出来可能存在的数字 27 may[b[i]]++; 28 29 while(b[i]*2<=4*a[N]){ 30 may[b[i]*2]++; 31 b[i]*=2; 32 } 33 while(b2[i]/2>=1){ 34 may[b2[i]/2]++; 35 b2[i]/=2; 36 } 37 38 } 39 40 int now=0; 41 for(int i=1;i<=4*a[N];i++){ 42 if(may[i]==N){ //不为偶数的 43 now++; 44 c[now]=i; 45 } 46 } 47 48 for(int k=1;k<=4*a[N]; ){ 49 if(may[k]!=N){ 50 now++; 51 c[now]=k; 52 } 53 k<<=1; 54 } 55 //f[i][j]表示前i个数，全部变成c[j]时，所需的能量 56 57 for(int j=1;j<=now;j++){ 58 for(int i=1;i<=N;i++){ //DP 59 int num=c[j]; 60 int ans=0; 61 62 if(may[num]==N){ //序列中的每个数都可以直升直降得到 63 64 if(num==a[i]) ans=0; 65 if(num>a[i]){ 66 int x=a[i]; 67 while(x!=num){ 68 x*=2; 69 ans++; 70 } 71 } 72 if(num
           
            a[i]){ 85 while(x!=num){ 86 x<<=1; 87 ans++; 88 if(x>num){ 89 ans=inf; 90 break; 91 } 92 } 93 } 94 if(ans==0&&num!=a[i]) 95 ans=inf; 96 if(x!=num){ 97 int ans1=0; 98 int x=a[i]; 99 while(x!=1){100 if(x==num) break;101 else{102 x>>=1;103 ans1++;104 }105 }106 while(x!=num){107 x<<=1;108 ans1++;109 }110 ans=min(ans,ans1);111 } 112 }113 f[2][j]=f[1][j]+ans;114 f[1][j]=f[2][j];115 f[2][j]=0;116 if(i==N) 117 ANS=min(ANS,f[1][j]);118 }119 }120 121 cout<