HDU 6374 度度熊拼三角

谁践踏了优雅 2021-11-11 05:50 204阅读 0赞

# 度度熊拼三角 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1764    Accepted Submission(s): 792**

**Problem Description**

度度熊有 N 根木棒，每根木棒的长度为ai。  
  
现在要挑选其中的三根，问能拼出的三角形的最大周长是多少。  
  
如果不能拼成任何一个三角形，输出 −1。

**Input**

多组数据（不超过10组）,读到EOF结束。  
  
对于每一组数据：  
  
第一行一个数 N 表示木棒数量。  
  
第二行一共 N 个数，描述每一根木棒的长度。  
  
1≤N≤1000  
  
木棒长度都是不超过100000的正整数

**Output**

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

**Sample Input**

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

**Sample Output**

-1
    22

**Source**

[2018 “百度之星”程序设计大赛 - 初赛（A）][2018 _ - _A]

AC源码：

#include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    #include<vector>
    using namespace std;
    #define  N  1007 
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	int n;
    	int a[N];
    	while(cin>>n){
    		bool flag = false;
    		for(int i=0;i<n;i++)
    			cin>>a[i];
    					if(n<3){
    			cout<<-1<<endl;
    			continue;
    		}
    		sort(a, a+n);
    		for(int i=n-1; i>=0; i--){
    			for(int j=i-1; j>=0; j--){
    				for(int k=j-1; k>=0; k--){
    					if(a[i]+a[j] > a[k] && a[i]+a[k] > a[j] && a[j]+a[k]>a[i]){
    						cout<<a[i]+a[j]+a[k]<<endl;
    //						cout<<"i:"<<i<<"    j:"<<j<<"    k:"<<k<<endl;
    						flag=true;	
    						break;
    					}
    				}
    				if(flag) break;
    			}
    			if(flag) break;
    		}
    		
    		if(flag==false){
    			cout<<-1<<endl;
    		}
    	}
    	return 0;
    }

[2018 _ - _A]: http://acm.hdu.edu.cn/search.php?field=problem&key=2018+%A1%B0%B0%D9%B6%C8%D6%AE%D0%C7%A1%B1%B3%CC%D0%F2%C9%E8%BC%C6%B4%F3%C8%FC+-+%B3%F5%C8%FC%A3%A8A%A3%A9&source=1&searchmode=source