2019中山大学程序设计竞赛 Triangle

今天水了一发hdu上的中山校赛这个题交了将近十遍才过......

就是说给 n 个木棍，如果能找出3个能组成三角形的木棍就输出yes 反之输出no

乍一看很简单一个排序遍历一遍就好了

但是n值太大了，我试了一下，就算不加sort都会TLE......

问了一下大神才想出这个关键的条件:

假设 a1=1，a2=2，a3=3 那么这是最小的三个不能组成三角形的木棍，

所以如果n=4，那么a4最小是a2+a3=5

n=5，a5最小是8

................

当n=47时，a47=4807526976 这是大于题目中所给的 2^32 的条件的所以如果输入的n>47就可以判断是yes了如果小于47 遍历一遍也不慢~

#include<bits/stdc++.h>

using namespace std;

int i,n,a[];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        int flag=;

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

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

        if(n>)

        cout<<"YES"<<endl;

        else

        {

        sort(a,a+n);

        for(i=n-;i>=;i--)

        {

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

            {

                flag=;

                break;

            }

        }

        if(flag)

        cout<<"YES"<<endl;

        else

        cout<<"NO"<<endl;

    }

    }

}

巴特西

2019中山大学程序设计竞赛 Triangle

最新文章

热门文章