ACM题关于n个数据,最后选出3个构成三角形,要求边长最大Description可怜的lpx终于在别人的帮助下追上了aqx,可是他那瘦弱的身体想要去强行从aqx那里抢回烟那是不可能的.aqx看着可怜的lpx实在不

Question

ACM题 关于n个数据,最后选出3个构成三角形,要求边长最大
Description
可怜的lpx终于在别人的帮助下追上了aqx,可是他那瘦弱的身体想要去强行从aqx那里抢回烟那是不可能的.aqx看着可怜的lpx实在不忍心继续欺负他,便随手扔出来一堆长短不一的木棍,让lpx从中挑出来三根木棍,组成一个三角形,如果这个三角形的周长最大,那么aqx将把烟还给lpx.哎,可怜的lpx.
Input
多组数据,每组数据一个n（5

Answer 1

排序用sort就好了……你的排序要确定是从大到小排的
然后看一下主算法.你的算法是O(n^3)的,对于n=100000的数据,肯定严重超时.
对于n=100000的数据,必须用O(nlogn)以下级别的算法解决.这个题是贪心,不是搜索.
说一下思路.
先从大到小排序,然后取最大的三条边判断三角形的条件.如果不能,则用第2大、第3大、第4大的三条边判断,如果还不行就用用第3大、第4大、第5大的三条边判断.什么时候可以了,三边之和就是要的周长最大值.
证明：
假设我有一个从大到小排好序的数组a[0...n-1].对于最大的三条边,如你所说,这里判断三角形的唯一条件就是a[0]=a[1]+a[2],则对于任何i,j,(i>=1,j>=2,i≠j),有a[1]>=a[i],a[2]>=a[j],因此a[0]>=a[i]+a[j].换句话说,如果最大的一条边不能跟第二大、第三大的两条边组成三角形,就一定不能与其他边组成三角形.因此这个最大边就应该被舍弃（想象这根棍子被扔了）.在剩下的n-1个棍子里的最大的三条边继续上面的算法,直到找到符合条件的三角形为止.证毕.