19 中山重现赛 1002 triangle

题意：给一组数据a[0]...a[n],  n<5e6, a[i]<2^31-1(1e9)判断是否存在三角形数

首先想到的是排序，若a[i]+a[i+1]>a[i+2] , 则存在三角形数， 但5e6的范围 肯定会T

借用杭师大某题思路  先构造最小不可能序列 a+b=c: 1 2 3 ；2 3 5；3 5 8；......明显就是斐波那契序列， 50组之后就到1e10了 , 即n>=50一定存在三角形数

剩下50个数排序就不会T了

还有要多组输入  用scanf 不然也会T

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<queue>

#include<stack>

#include<list>

#include<set>

using namespace std;

typedef int ll;

typedef pair<ll,ll> p;

typedef long double ld;

#define mem(x) memset(x, 0, sizeof(x))

#define me(x) memset(x, -1, sizeof(x))

#define fo(i,n) for(i=0; i<n; i++)

#define sc(x) scanf("%lf", &x)

#define pr(x) printf("%lld\n", x)

#define pri(x) printf("%lld ", x)

#define lowbit(x) x&-x

const ll MOD = 1e18 +;

const ll N = 6e6 +;

ll a[N];

int main()

{

    ll i, j, k, l=;

    ll n, m, t;

    while(~scanf("%d", &n))

    {

        for(i=; i<n; i++)

            scanf("%d", &a[i]);

        if(n>=) {printf("YES\n");continue;}

        sort(a,a+n);

        ll f=;

        for(i=; i<n-; i++)

        {

            if(a[i]+a[i+]>a[i+])

            {

                f=;

                break;

            }

        }

        if(f) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}