解题思路

解法一

设三条线段的长度为 $x \le y \le z$。如果它们不能构成非退化三角形，那么长度为 $x-1, y, z$ 或 $x, y, z+1$ 的线段也不能构成非退化三角形。因此，我们不需要尝试所有组合。如果我们把 $y$ 作为中间长度，那么我们需要尝试小于等于 $y$ 的最大 $x$ 和大于等于 $y$ 的最小 $z$。最简单的做法是：对线段长度排序，然后检查所有连续的三条线段。

时间复杂度：$O(n \log n)$

解法二

根据解法一中的观察，如果我们尝试构造一个序列，使得排序后任意连续三条线段都构成退化三角形，那么这个序列会是斐波那契数列：$1, 1, 2, 3, 5, 8, 13, \dots$。斐波那契数列增长非常快，$fib(45) = 1134903170$。这意味着，当 $n \ge 45$ 时，答案一定是 "YES"。当 $n < 45$ 时，我们可以使用朴素的 $O(n^3)$ 算法或解法一。

设 $x$ 是满足如下不等式的数：

• $fib(x) \le \max A_i$
• $fib(x+1) > \max A_i$

时间复杂度：$O(x^3)$ 或 $O(x \log x)$

代码实现（解法一）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    for (int i = 0; i + 2 < n; ++i) {
        if (a[i] + a[i + 1] > a[i + 2]) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
    return 0;
}

代码实现（解法二）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n >= 45) {
        cout << "YES\n";
        return 0;
    }

    sort(a.begin(), a.end());

    for (int i = 0; i + 2 < n; ++i) {
        if (a[i] + a[i + 1] > a[i + 2]) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
    return 0;
}