三角形的周长
- Time Limit: 2000/1000ms (Java/Others)
- Problem Description:
有 n 根棍子, 棍子 i 的长度为 ai, 想要从中选出 3 根棍子组成周长尽可能长的三角形. 请输出最大的周长, 若无法组成三角形则输出 0.
Input:
输入包含多组测试, 每组测试第一行输入一个整数 n(3n10^5); 第二行输入 n 个整数 ai(1ai10^6);
Output:
对于每组测试, 输出一个数字, 表示最大周长, 如果无法组成三角形, 则输出 0.
- Sample Input:
- 5
- 2 3 4 5 10
- 4
- 5 4 20 10
- Sample Output:
- 12
- 0
解题思路: 这是挑战程序设计竞赛 (第二版)里的一道题, 书中说了一种解法 O(n3), 另外, 还特意说明另有一种 O(nlogn) 的解法, 留给读者思考. 但对于此题来讲, 由于给出 n 的范围最大值是 10^5, 所以不能用 O(n3), 而应该用 O(nlogn)的解法.
我们知道组成三角形的充要条件是: 最长的边小于其余两边之和; 不难想到, 可以三重循环枚举所有的选择方案, 再判断能否组成三角形, 最后找出最大的周长即可. 不过此算法时间复杂度太大, 会超时!
另一种方法是先把棍子进行排序, 然后只比较相邻的三个棍子, 最后选择最大的周长. 这样只需一次循环即可. 为什么这样就可行? 理由: 假如棍子已经升序排序了, 有 a<b<c<d, 如果有 a+b>c 且 a+b>d, 程序中并没有比较 a+b 和 d, 那么是否会漏掉这种情况导致错误呢, 不会的, 因为如果 a+b>d 的话, 那么 b+c 也一定大于 d, 而 a+b 又小于 b+c, 所以 a+b 和 d 后面的数的比较是多余的, 而且若这两种情况同时成立, 我们也只能取后一种的情况, 因为要得到最长的周长!!! 这样就只需比较相邻的三个棍子即可.
- #include<bits/stdc++.h>
- using namespace std;
- int a[1000005],n;
- int main(){
- while(cin>>n){
- for(int i=0;i<n;++i)
- cin>>a[i];
- sort(a,a+n);// 默认升序排序
- int ans=0;
- for(int i=0;i<n-2;++i){
- int len=a[i]+a[i+1]+a[i+2];// 三角形的周长
- if(a[i]+a[i+1]>a[i+2])ans=max(ans,len);// 证明出来的结论
- }
- cout<<ans<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2587871.html