牛客编程巅峰赛S2第2场 - 钻石&王者 A-牛牛切木棒

A牛牛切木棒
这格式真难调

分析

众所周知，假设 是三角形的三条边，那么一定满足任意两条边之和大于第三条边。假设我们把当前的长度为a的线段分成了p段，从小到大分别为 ,那么如果不能构成三角形，一定满足 ，因为要尽可能多的分段，那么就得尽可能的小。那就可以直接把b数组预处理出来，能分则分，同时记录一个变量表示分的段数

代码

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    long long f[70]={1,1};
    int stick(long long a) {
        // write code here
        for (int i=2;i<64;i++) f[i]=f[i-1]+f[i-2];
        int cnt=0,now=0;
        while(a>=f[now]) now++,cnt++,a-=f[now-1];

        return cnt;
    }
};