牛牛切木棒

链接：https://ac.nowcoder.com/acm/contest/22425/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

有一根长度为a(3≤a≤1e18)(3 leq a leq 1e18)(3≤a≤1e18)的木棒，现在想将木棒分成一些段（每段木棒长度必须为整数），使得分隔后的木棍中，任意三段都不能构成三角形，求木棒最多被分成几段呢？

示例1

输入

复制 5

5

返回值

复制 3

3

说明

可以分成1 1 3三段
 

备注:

斐波那契数列。

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    int stick(long long a) {
        if(a <= 3) return 0;
        std::vector<long long> num = {1,1};
        int i = 2;
        a -= 2;
        while(a > 0)
        {
            long long d = (num[i - 1] + num[i - 2]);
            if(d <= a)
            {
                num.push_back(d);
                i++;
            }
            a -= d;
        }
        return i;
    }
};