斐波那契的拆分100%AC代码

解题思路

一、题目到底要什么？
·给你一个数 n，把它拆成斐波那契数相加，并且满足：
·用的数字个数最少（最重要）
·个数一样时，最右边的数字尽量大
·最后输出格式：n=a+b+c+...（从小到大）

二、核心解法：贪心算法（一句话）
每次都选 ≤ 当前剩下数字的最大斐波那契数，一直减到 0 为止。
这个方法天然满足：个数最少 + 右边最大。

三、代码逻辑分步解释

1. 预处理斐波那契数
   先算出所有 ≤1e9 的斐波那契数（只有 40 多个）
   存在数组 f[] 里，方便后面直接用
2. 处理每个输入 n
   拿 n 开始，从最大的斐波那契数往下找
   只要这个数 ≤ 剩下的值，就选中它，并从 n 里减掉它
   重复直到减到 0
3. 调整顺序 + 输出
   选出来的数是从大到小的
   反转一下变成从小到大
   按格式输出：n=数字+数字+...

四、极简逻辑总结（最核心）
·先生成斐波那契数组
·从大到小贪心选取（保证个数最少、右边最大）
·反转顺序（满足输出要求）
·按格式输出

五、为什么这个逻辑是对的？
·每次选最大的 → 用的数字最少
·先选大的后选小的 → 天然满足右边尽量大
·斐波那契数列的性质保证：这种拆分一定存在且唯一最优
·超短记忆版思路
·预处理斐波那契数 → 从大往小拿 → 反转输出

100%AC代码：

#include<bits/stdc++.h>
using namespace std;
long long f[50];
int l;
void ff(){
    f[0]=1,f[1]=1,l=2;
    while(f[l-1]<=1e9){
        f[l]=f[l-1]+f[l-2];
        l++;
    }
}

int main(){
    ff();
    int t;
    cin>>t;
    while(t--) {
        long long n,m,a[50];
        int s=0;
        cin>>n;
        m=n;
        for(int i=l-1;i>=0;i--){
            if(f[i]<=m){
                a[s++]=f[i];
                m-=f[i];
            }
        }
        reverse(a,a+s);
        cout<<n<<"=";
        for(int i=0;i<s;i++){
            if(i){
                cout<<"+";
            }
            cout<<a[i];
        }
        cout<<endl;
    }
}