Problem 1274 - 可怜的lpx

Problem 1274 - 可怜的lpx

Time Limit: 1000MS   Memory Limit: 65536KB   

Description

可怜的lpx终于在别人的帮助下追上了aqx，可是他那瘦弱的身体想要去强行从aqx那里抢回烟那是不可能的。aqx看着可怜的lpx实在不忍心继续欺负他，便随手扔出来一堆长短不一的木棍，让lpx从中挑出来三根木棍，组成一个三角形，如果这个三角形的周长最大，那么aqx将把烟还给lpx。哎，可怜的lpx。。。

Input

多组数据，每组数据一个n（5<= n <=10^6），代表有n根木棍。
接下来n个整数Xi，代表第i根木棍的长为Xi （1<=Xi<=10^6）。

Output

能组成最大的三角形周长（保证有解）

Sample Input

4
1 2 3 4

Sample Output

9

      很贪心的思想，组成最长周长的3边一定相邻。这样就可以O（N）的枚举了。

 

#include <iostream>

#include <stdio.h>

#include <queue>

#include <stdio.h>

#include <string.h>

#include <vector>

#include <queue>

#include <set>

#include <algorithm>

#include <map>

#include <stack>

#include <math.h>

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std ;

typedef long long LL ;

const int Max_N= ;

int N ,num[Max_N] ;

int cmp(int a ,int b){

    return a>b ;

}

inline int ok(int a ,int b ,int c){

    return b+c>a ;

}

int gao(){

    int i= ;

    while(i<=N-){

        if(ok(num[i],num[i+],num[i+]))

             return num[i]+num[i+]+num[i+] ;

        i++ ;

    }

}

int main(){

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

         for(int i= ;i<=N; i++)

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

         sort(num+,num++N,cmp) ;

         printf("%d\n",gao()) ;

    }

    return  ;

}