题目描述
机器猫要在电脑前打字。一共需要打 𝑛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;
}