构造三角形 - 帖子

题意

给定根木棍，木棍的长度范围是，问：根据这些木棍，是否一定能选出三根构造出一个三角形？

题解

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

若根木棍从小到大的长度依次为：，即 .任选三根木棍的长度为。当此三根木棍无法构造出三角形时，必定存在.因而当根木棍无法构造出一个三角形时，必定存在如下关系：.

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

当时，我们根据这些木棍无法构造出一个三角形，否则我们一定能够构造出一个三角形.

显然，具备指数级别的增长速度。和斐波那契数列相似，时，已超过数据范围.

判定最坏情况下无法构造出三角形的时间复杂度为：，显然符合时间限制.

注：的增长速度为指数级别，当时应直接，否则可能会爆.

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()