度度熊拼三角

Accepts: 2536

Submissions: 4433

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

度度熊有 NNN 根木棒，每根木棒的长度为aia_ia​i​​。

现在要挑选其中的三根，问能拼出的三角形的最大周长是多少。

如果不能拼成任何一个三角形，输出 −1-1−1。

Input

多组数据（不超过101010组）,读到EOF结束。

对于每一组数据：

第一行一个数 NNN 表示木棒数量。

第二行一共 NNN 个数，描述每一根木棒的长度。

1≤N≤10001 \leq N \leq 10001≤N≤1000

木棒长度都是不超过100000100000100000的正整数

Output

对于每一组数据，输出一个数表示答案。

Sample Input

Copy

3
1 1 100
7
1 9 9 90 2 2 4

Sample Output

Copy

-1
22

三层for循环超时。。。。。贡献了一发。。。。

既然是找三角形周长最大  ， 那当然要尽可能从大的数里找符合构成三角形的 ， 如果找到直接跳出就好

代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n , a[1000] , ret;
    while(~scanf("%d" , &n))
    {
        int ans = 0; 
        int flag = 0;
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d" , &a[i]);
        }
        sort(a , a+n);
        if(n < 3)
        {
            flag = 2;
        }
        else
        {
            for(int i = n-1 ; i >= 0 ; i--)
            {
                if(a[i]+a[i-1]>a[i-2])
                    if(a[i]+a[i-2]>a[i-1])
                        if(a[i-1]+a[i-2]>a[i])
                        {
                            flag = 1;
                        ans=a[i]+a[i-1]+a[i-2];
                        break;
                        }
            }
        }
    
        if(flag != 1)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n" , ans);
        }
        
    }
    return 0;
}