首页 / 更多教程 / 2019中山大学程序设计竞赛 Triangle

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2019中山大学程序设计竞赛 Triangle，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含805字，纯文字阅读大概需要2分钟。

内容图文

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[5000005];

int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        
        
        int flag=0;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        if(n>47)
        cout<<"YES"<<endl;
        else
        {
        sort(a,a+n);
        for(i=n-1;i>=2;i--)
        {
            if(a[i-2]+a[i-1]>a[i])
            {
                flag=1;
                break;
            }
        } 
        if(flag)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }    
    }
}

 

内容总结

以上是互联网集市为您收集整理的2019中山大学程序设计竞赛 Triangle全部内容，希望文章能够帮你解决2019中山大学程序设计竞赛 Triangle所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/831604.html

来源：【匿名】