19 中山重现赛 1002 triangle

阅读原文时间：2024年06月17日阅读：1

题意：给一组数据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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef int ll;
typedef pair 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=) {printf("YES\n");continue;}
sort(a,a+n);
ll f=;
for(i=; ia[i+])
{
f=;
break;
}
}
if(f) printf("YES\n");
else printf("NO\n");
}
return ;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章