1604: Operations

时间限制: 2 Sec  

内存限制: 128 MB

提交: 313  

解决: 97

[ ][ ][ ]

题目描述

 You can perform the following operations.

• i = i+1;
• i = i-1;
• i = i/2 if i is even

The number i is integer. Find the minimal number of operations to get 0. 

输入

 Each line contains an N,  1 ≤ N ≤ 2000000。 Process to end of file.

输出

 For each case, print one line containing an integer which is the minimal number of operations from N to 0.

样例输入

41559

样例输出

369

提示

来源

这题一开始想的是BFS暴力搜索，试了一下

2000000，感觉还不错，结果一提交TLE，然后想到打表，结果codeblocks打崩溃了表也没打完，估计打完了也会超过代码长度无法提交，这个时候我意识到了问题的不简单，之后发现这可能是一道贪心题，如果是偶数，为了让他变得更小，一定要除2，如果是奇数，可能要加一或者减一，问题就在这，究竟是加一之后不断初二还是减一之后不断除二，这里打表，判断是加一之后更小还是减一之后更小，之后特判一下1就可以了；

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

#include<iostream> #include<cstring> #include<cstdio> using  namespace  std; const  int  N = 2000000+5; int  a[N]; void  Init(){      memset (a,0, sizeof (a));      for ( int  i=2;i<N;i+=2){          if (i%2==0){              int  tmp = i;              while ( true ){                  tmp/=2;                  if (tmp%2)  break ;              }              a[i] = tmp;          }      } }   int  main(){      Init();      int  n;      while ( scanf ( "%d" ,&n)==1){          int  cnt = 0;          while ( true ){              if (n==1){cnt++; break ;}              if (n%2==0){n/=2;cnt++;}              else {                  n = a[n-1]>a[n+1]?n+1:n-1;                  cnt++;              }          }          printf ( "%d\n" ,cnt);      }      return  0; }