题意
有长度为n的木棍 最多能将其分成多少段 使得任意三段无法构成三角形
思路
很容易想到三角形性质是任意两边之和大于第三边 反之就是小于等于第三边 容易联想到斐波那契数列 某一项为前两项之和 里面都是符合题意的情况 由于要算多少个 我们求一个前缀和 计算需要多少长度才能分成该段 取最大值就是答案了 范围太大 要开ull 直接上java大数也行
代码
#include <bits/stdc++.h> using namespace std; #define ULL unsigned long long ULL f[105]; int main(){ ios::sync_with_stdio(0); f[1] = 1,f[2] = 1; for(int i = 3;i <= 91;i ++){ f[i] = f[i - 1] + f[i - 2]; } for(int i = 2;i <= 91;i ++){ f[i] += f[i - 1]; } int t; cin >> t; while(t --){ ULL n; cin >> n; int res = 1; for(int i = 1;i <= 91;i ++){ if(n >= f[i]){ res = max(res,i); }else{ break; } } cout << res << '\n'; } }