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

本文主要是介绍2018 “百度之星”程序设计大赛 - 初赛（A）度度熊拼三角，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

度度熊拼三角

 

 Accepts: 2536

 

 Submissions: 4433

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

 

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

Problem Description

度度熊有 NN 根木棒，每根木棒的长度为a_ia​i​​。

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

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

Input

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

对于每一组数据：

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

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

1 \leq N \leq 10001≤N≤1000

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

Output

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

Sample Input

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

Sample Output

Copy

-1
22

 

AC了之后看网上的题解，发现大家都是用的贪心。。。。。

仔细一想，还真是可以贪心，自己想复杂了，直接用的二分过的。

就两个一起贴出来吧。

 

二分：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<iostream>
#include<cmath>
#include<stack>
#include<string>
using namespace std;int a[100005];
int sum[100005];int main()
{int n;while(~scanf("%d",&n)){for(int i=0; i<n; i++)scanf("%d",&a[i]);sort(a,a+n);int maxs=-1;for(int i=0; i<n-2; i++)for(int j=i+1; j<n-1; j++){int l=j+1;int r=n-1;while(l<=r){int mid=(l+r)/2;if(a[mid]>a[i]+a[j])r=mid-1;elsel=mid+1;if(a[mid]>abs(a[i]-a[j])&&a[mid]<a[i]+a[j])maxs=max(maxs,a[mid]+a[i]+a[j]);}}cout<<maxs<<endl;}return 0;
}

贪心：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<iostream>
#include<cmath>
#include<stack>
#include<string>
using namespace std;int a[100005];
int sum[100005];int main()
{int n;while(~scanf("%d",&n)){for(int i=0; i<n; i++)scanf("%d",&a[i]);sort(a,a+n);int flag=0;for(int i=n-1; i>=2; i--)if(a[i]<a[i-1]+a[i-2]&&a[i-1]<a[i]+a[i-2]&&a[i-2]<a[i]+a[i-1]){flag=1;cout<<a[i]+a[i-1]+a[i-2]<<endl;break;}if(!flag)cout<<"-1"<<endl;}return 0;
}

 

这篇关于2018 “百度之星”程序设计大赛 - 初赛（A）度度熊拼三角的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---