首页程序设计基础R - 2024 级程序设计基础复习赛
时间限制 内存限制
1000 ms 65536 KB

# 题目描述

小 P 获得了一根木棍，其长度为 xx。由于其实在是太长了，于是小 P 想将它分割成多段。由于小 P 具有强迫症，因此分割后每段木棍的长度都应为正整数，且任意三段木棍都不能组成一个三角形。请编写一段程序，告诉小 P 其最多能将木棍分割成多少段。

# 输入格式

第一行给出一个整数 TT，代表输入组数。其中，1≤T≤1061≤T≤10^6。

之后共输入 TT 组数据，对于每一组输入，将给出一个整数 xx。其中，0<x≤10120<x≤10^{12}。

# 输出格式

一行整数，为小 P 最多能将木棍分割成多少段。

每组输出之间用换行间隔，具体含义见题目描述。

# 输入样例

2
2
19

# 输出样例

2
5

# 样例解释

对于第一组数据，可将木棍分为 22 个长度分别为 1,11,1 的木棍；

对于第二组数据，可将木棍分为 55 个长度分别为 3,8,1,2,53,8,1,2,5 的木棍；

# 题解：二分查找

不难得知，要让任意两根木棍都不能组成三角形，且木棍数量要尽量多，我们就按照斐波那契数列切割木棍。

同时我们预处理斐波那契数列的前缀和，然后二分查找最大的不超过 xx 的项即可。

时间复杂度：O(Tlog⁡n)O(T \log n)，其中 nn 是不超过 101210^{12} 的斐波那契数列项数。

参考代码：

#include <stdio.h>
typedef long long ll;
int cnt;
ll fib[10010], prefix[10010];
void Init(ll lim)
{
    fib[1] = fib[2] = 1;
    prefix[1] = 1, prefix[2] = 2;
    for (int i = 3; fib[i - 2] + fib[i - 1] <= lim; ++ i)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
        prefix[i] = prefix[i - 1] + fib[i];
        cnt = i;
    }
    return;
}
int main()
{
    // freopen("K.in", "r", stdin);
    // freopen("K.out", "w", stdout);
    Init(1e12);
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        ll x;
        scanf("%lld\n", &x);
        int l = 1, r = cnt;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (prefix[mid] <= x)
                l = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}