更好的阅读体验

题目概要

题目描述

给一个数$k$，问最少可以用几个斐波那契数加加减减凑出来
例如
$$ 10=5+5 \\\\ 19=21-2 \\\\ 17=13+5-1 \\\\ 1070=987+89-5-1 \\\\ $$

样例输入

1
1070

样例输出

4

数据范围

$$ k \le 10^{17} $$

多组数据,不超过$10$组.

解题报告

题意理解

给一个数$k$，问最少可以用几个斐波那契数加加减减凑出来.

算法解析

首先我们得知道,因为斐波那契数列,有如下这个特殊数字.
$$ a_0=0,a_1=1,a_2=1,a_3=2 \\\\a_n=a_{n-1}+a_{n-2} \quad n \ge 2 $$
那么一个数字,总能被几个斐波那契数组合而成.

证明不太会,大佬可以在下面留言,教教我.

我们接着理解,对于一个整数,它的斐波那契数表示如下.
$$ x=a_1 \pm a_2 \pm a_3 \pm \dots \pm a_{cnt} \\\\其中a_i为斐波那契数 $$
而题目的要求,就是让我们找到这个最小的$cnt$

假如说,我们发现,在这个表达数列之中,有两个数$a,b$满足.
$$ 定义:Rank(a)表示为a在斐波那契数列中的位置 \\\\若Rank(a)=Rank(b)+1 \quad 或者 \quad Rank(b)=Rank(a)+1 $$
那么,我们可以使用,一个数$c$,代替$a,b$.
$$ c=a+b $$
或者说,本来表达数列是.
$$ x=a+b \Rightarrow x=c \\\\x=p-a-b \Rightarrow x=p-c \\\\ $$
比如说.
$$ x=14=1+13=1+5+8 \\\\13=15+8 \\\\1,5,8,13,都是斐波那契数 $$
这有什么用处?

这可以让我们推出贪心

对于一个数$x$，我们找到与$x$差值最小的斐波拉契数，将新的$x$赋为差值，每次进行这个操作，统计次数，直到$x$为$0$，输出次数。

这个的证明,其实在上面就已经体现了.
$$ f[x]=min(f[p]-x,x-f[p-1]) \\\\p为大于等于x,中最小的数 \\\\p-1自然就是小于等于x,中最大的数 \\\\ $$

代码解析

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=110;
int f[N],x,n;
inline int check(int x)
{
    int cnt=0,p=0;
    while(x)
    {
        p=lower_bound(f+1,f+1+98,x)-f;//大于等于x中最小的那一个数
        x=min(x-f[p-1],f[p]-x);//p-1为小于等于x中最大的那一个数
        cnt++;
    }
    return cnt;
}
inline void init()
{
    scanf("%lld",&n);
    f[1]=1;
    for(int i=2; i<=98; i++)//预处理斐波那契数
        f[i]=f[i-1]+f[i-2];
    while(n--)
    {
        scanf("%lld",&x);
        printf("%lld\n",check(x));
    }
}
signed main()
{
    init();
    return 0;
}

感谢five50大佬的题解,让我会做本题