Codeforces Testing Round #3 B. Pairs of Numbers【dfs】【枚举】

题目链接：https://codeforc.es/problemset/problem/134/B
题目大意：假定我们有一个数对$(a,b)$，我们可以得到下一个新的数对$(a+b,b)$或者$(a,a+b)$，初始数对为$(1,1)$，问要得到一个数对中要有一个值为$n$，至少需要多少次操作。
思路：$n$的范围只是在$1e6$，所以我们可以假定答案为$(n,m),m<n$，暴力枚举$m$，每次类似于辗转相除法的形式计算次数。
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int nn;
void dfs(int n,int m,int & cnt)
{
    if(m==1){//初始情况下，n是从1每次加1得到n的
        cnt+=n-1;
        return ;
    }
    if(m==0){//这种情况是不合法的，cnt赋不合法值直接返回
        cnt=nn;
        return ;
    }
    cnt+=n/m;
    n%=m;
    dfs(m,n,cnt);
}
int main()
{
    
    cin>>nn;
    int ans=nn-1;
    for(int i=1;i<nn;i++){
        int cnt=0;
        dfs(nn,i,cnt);
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}

最后

以上就是平常学姐为你收集整理的Codeforces Testing Round #3 B. Pairs of Numbers【dfs】【枚举】的全部内容，希望文章能够帮你解决Codeforces Testing Round #3 B. Pairs of Numbers【dfs】【枚举】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。