HNUSTOJ 1604:Operations

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.

样例输入

样例输出

提示

来源

2014年湖南科技大学校赛

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

#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;

}

巴特西

HNUSTOJ 1604:Operations

1604: Operations

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章