题意

​ 给定$n(n \ge 3)$根木棍，木棍的长度范围是$[l ,r]$，问：根据这些木棍，是否一定能选出三根构造出一个三角形？

题解

​ 思考一下，$n$根木棍在什么情况下无法构造出三角形？

​ 若$n$根木棍从小到大的长度依次为：$a_1,a_2,...,a_n$，即 $\forall i \in [1,n-1],a_i \le a_{i+1}$.任选三根木棍的长度为$a_i,a_j,a_k \; (1 \le i < j <k \le n)$。当此三根木棍无法构造出三角形时，必定存在$a_i + a_j \le a_k$.因而当$n$根木棍无法构造出一个三角形时，必定存在如下关系：$a_{i - 2} + a_{i - 1} \le a_i (i \ge 3)$.

​ 在最坏情况下，当给定木棍无法构造出一个三角形时，它们的数学关系满足如下条件：

$$a_{i} = \begin{cases} l , \; i \le 2 \\ a_{i - 2} + a_{i - 1} \; ,i \ge3 \end{cases}$$

​ 当$a_{n} \le r$时，我们根据这些木棍无法构造出一个三角形，否则我们一定能够构造出一个三角形.

​ 显然，$a_{i}$具备指数级别的增长速度。和斐波那契数列相似，$n \ge 80$时，$a_n$ 已超过数据范围.

​ 判定最坏情况下无法构造出三角形的时间复杂度为：$O( T * log(r))$，显然符合时间限制.

注：$a_{i}$的增长速度为指数级别，当$a_{i} > r$时应直接$break$，否则可能会爆$long \; long$.

Code

C \ C++

#include<stdio.h>
typedef long long i64;

int calc(i64 l,i64 r){
    int res = 3;
    i64 a = l,b = l,c = l + l;
    while(c<=r){
        i64 t = b + c;
        a = b,b = c,c = t;
        res++;
    }
    return res;
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        i64 k,l,r;
        scanf("%lld %lld %lld",&k,&l,&r);
        printf("%s\n",k>=calc(l,r)?"YES":"NO");
    }
}

Python

import sys

input = lambda: sys.stdin.readline().strip()
def main():
    import sys
    data = sys.stdin.read().split()
    T = int(data[0])
    ptr = 1
    res = []
    for _ in range(T):
        k = int(data[ptr])
        l = int(data[ptr + 1])
        r = int(data[ptr + 2])
        ptr += 3
        # 构建最大三角形无法成立的集合
        f = 2  # 初始有两个元素 l, l
        s1 = l
        s2 = l
        while True:
            s3 = s1 + s2
            if s3 > r:
                break
            f += 1
            s1 = s2
            s2 = s3
        if k > f:
            res.append("YES")
        else:
            res.append("NO")
    print('\n'.join(res))

if __name__ == "__main__":
    main()