嵊州D1T3 睡美人航班

绝地灬酷狼 2021-11-22 17:38 192阅读 0赞

# 嵊州D1T3 #

## 睡美人航班 ##

不知不觉中，我对她的爱意已经达到了 n。

是这样子的，第 1 分钟，我对她的爱意值是 (1, 1)。

假如当第 x 分钟时我对她的爱意值是 (a, b)，那么第 x + 1 分钟我对她的爱意值就是 (a + b, b) 或者 (a, a + b)。

在关注着她的时候，我已然忘记了时间。

现在我想知道，这时候航班已经至少起飞了多久？

爱意为 n，也就是说 a + b = n。

## Input ##

一行一个整数 n。

## Output ##

一行一个整数表示答案。

## Examples ##

<table style="width:523px;"> 
 <tbody> 
  <tr> 
   <td>sleepingbeauty.in</td> 
   <td>sleepingbeauty.out</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

## Notes ##

对于所有数据，满足 2 ≤ n ≤ 106

Task1\[30%\]

n ≤ 20

Task2\[50%\]

n ≤ 103

Task3\[70%\]

n ≤ 104

Task4\[100%\]

无特殊限制

--------------------

## solve！ ##

这道题题挺简单的（虽然我没做出来）

没事！这不是最后的考试，我也还有机会！

看一眼题，先定义个gcd(a,b)再说

第二，那个灵力值的大小不重要，重要的是：

1、起始值

2、每个梦都要做（才能知道最多的事情嘛）

（好贪心哟(＾Ｕ＾)ノ~ＹＯ）

#include<bits/stdc++.h>
    using namespace std;
    const int inf = 0x3f3f3f;
    int n,a=0,b=0,nowtime=1,mintime=inf;
    int ay(int a,int b)
    {
        if(b) 
            return ay(b,a%b)+a/b;
        else 
            if(a>1) return inf;
            else return -1;
        
    }
    
    int main()
    {
        //freopen("sleepingbeauty.in","r",stdin);
        //freopen("sleepingbeauty.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            mintime=min(mintime,ay(n,i));    
        printf("%d",mintime);
        return 0;
    }
    /*
    另一种方法
    ay(){
    if(a+b>n) return;
    nowtime++;
    if(a+b==n) mintime=min(mintime,nowtime);
    ay(a+b,b);
    ay(a,a+b); 
    nowtime--;
    */

有一点我好傻：

>     if(b) 
>         return ay(b,a%b)+a/b;
>     else 
>         if(a>1) return inf;
>         else return -1;

其实可以很简单的用两个三目运算符的。。。

>  return b ? ay(b, a % b) + a / b : a > 1 ? inf : -1;

有的时候要相信自己嘛！

运行通过，再看看数据也没有什么特别大的。行吧！

转载于:https://www.cnblogs.com/send-off-a-friend/p/11172870.html