Chemistry

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

input

3
3 5 6

output

样例解释：

第一个样例能量值全部为成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<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<cmath>
  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]){
 73                     int x=a[i];
 74                     while(x!=num){
 75                         x/=2;
 76                         ans++;
 77                     }
 78                 }
 79             }
 80             //*********
 81             else{//有的数字必须先降再升可以达到 
 82                 int x=a[i];
 83                 if(num==a[i]) ans=0;
 84                 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<<ANS;
122     return 0;
123 }