构造三角形

admin 2024-10-20 14:42:08

题意

​ 给定根木棍,木棍的长度范围是,问:根据这些木棍,是否一定能选出三根构造出一个三角形?

题解

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

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

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

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

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

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

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

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