time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn’t accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.
Mahmoud should use exactly 3 line segments, he can’t concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.
Input The first line contains single integer n (3?≤?n?≤?105) — the number of line segments Mahmoud has.
The second line contains n integers a1,?a2,?…,?an (1?≤?ai?≤?109) — the lengths of line segments Mahmoud has.
Output In the only line PRint “YES” if he can choose exactly three line segments and form a non-degenerate triangle with them, and “NO” otherwise.
Examples input 5 1 5 3 2 4 output YES input 3 4 1 2 output NO Note For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.
【題目鏈接】:http://codeforces.com/contest/766/problem/B
【題意】 給你n條邊; 問你能不能從中挑出3條邊來組成一個三角形;(只要是三角形就行)
【題解】 可以這樣; 設 c<=b<=a 先把邊的長度升序排; 如果是三角形那么； a+b>c a+c>b即c>b-a b+c>a即c>a-b 這里b-a是個負數,所以不用理他 只考慮a-b就好; 而想讓a-b最小,肯定是選長度相鄰的兩條邊; 這樣從大到小,維護i..n這個區間范圍內a-b的最小值mi; 看看a[i]是不是大于mi;一旦有符合的就ok了; (至于a+b>c,因為a和b都在i..n這個范圍內選,所以a+b>c肯定成立的) 【完整代碼】
#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 1e5+100;int a[MAXN],n;int main(){ //freopen("F://rush.txt","r",stdin); rei(n); rep1(i,1,n) rei(a[i]); sort(a+1,a+1+n); int d = a[n]-a[n-1]; rep2(i,n-2,1) { if (d<a[i]) { puts("YES"); return 0; } d = min(d,a[i+1]-a[i]); } puts("NO"); return 0;}新聞熱點
疑難解答
