题目描述

机器猫要在电脑前打字。一共需要打 𝑛n 个字，但现在文档里只有一个字。

机器猫有两种操作可以做。假设现在已经有 𝑥x 个字，机器猫可以选择：

• 往文档最后加一个字。字数变成 𝑥+1x+1。
• 把文档复制粘贴一遍。字数变成 2𝑥2x。

问机器猫至少需要多少次操作，才能得到恰好 𝑛n 个字。

输入格式

仅一行，一个正整数 𝑛n。

输出格式

仅一行，一个正整数，表示最少操作次数。

输入输出样例

输入 #1复制

16

输出 #1复制

4

输入 #2复制

5

输出 #2复制

3

说明/提示

样例解释

样例数据1，1→2→4→8→161→2→4→8→16，共 4 步。

样例数据2，1→2→4→51→2→4→5，共 3 步。

数据规模与约定

对于 100%100% 的数据，𝑛≤106n≤106。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
int n,m,t,d;
int a[N],b[N];
int f[N];
string sa,sb;

signed main(){
	cin>>n;
	f[1]=0;   //文档里已经有一个字了，初始化一个字为0； 
	for(int i=2;i<=n;i++){
		if(i%2==0)f[i]=min(f[i-1],f[i/2])+1; //偶数的时候才存在恰好的情况 
		else f[i]=f[i-1]+1;
	}
	cout<<f[n]<<endl;
}