2018 “百度之星”程序设计大赛 - 初赛（A）P1001度度熊拼三角（贪心）

problem

• 给定n根棍子。在其中选三根拼成最大周长三角形的周长。不能拼出三角形输出-1.

solution

先对数组进行排序，并利用贪心算法先取得最长的一根棍子，之后的两根依次取最长的棍子，如果这样构不成三角形，那么以最长棍子最为三角形中最长的一条边是不行的,至于为什么这样，可以举个例子,在2,3,4,5,7,8,20中我们按照刚才的想法依次找到了20,8,7但是20>7+8,所以20,8,7构不成三角形，如果这时不放弃20，仍将20作为三角形中最长的边，那么在剩下的棍子中肯定找不出满足条件的两个棍子，因为7和8就是除了20以外最长的根子了，他俩都无法和20组成三角形，那么其他的两根组合肯定就不行了.

codes

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n; i++)cin>>a[i];
        sort(a+1,a+n+1);
        bool isok = false;
        for(int i = n; i >= 1; i--){
            if(a[i]<a[i-1]+a[i-2]){
                isok = true;
                printf("%d\n", a[i]+a[i-1]+a[i-2]);
                break;
            }
        }
        if(!isok)printf("-1\n");
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81586326