ACM----三角形(有n根棍子，棍子i的长度为ai，想要从中选出3根棍子组成周长...)--golang

有n根棍子，棍子i的长度为ai。想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长，若无法组成三角形则输出0。

限制条件

3 ≤ n ≤ 100

1 ≤ ai ≤ 10^6 输入

n = 5

a = {2,3,4,5,10}

输出

12（选择3、4、5时）

输入

n = 4

a = {4,5,10,20}

输出

0(无论怎么选都无法组成三角形)

这是《挑战程序设计竞赛(第二版)》里的一道题，书中说了一种解法O(n³)，另外，还特意说明另有一种O(nlogn)的解法，留给读者思考。下面是两种解法。

三角形性质：两边之和大于第三边 三个for循环就可以解决，然后看看能不能组成三角形

// 暴力解法 n³ func res(n int, a []int) int { ans := 0 //答案 for i := 0; i < n; i++ { for j := i + i; j < n; j++ { for k := j + 1; k < n; k++ { l := a[i] + a[j] + a[k] // 周长 maxNum := max(a[i], max(a[j], a[k])) rest := l - maxNum //其余两根棍子的长度之和 //如果可以构成三角形，则更新最大周长 if rest > maxNum { ans = max(ans, l) } } } } return ans } func max(first int, args ...int) int { for _, v := range args { if first < v { first = v } } return first }

第二种解法 排序+判断 [公式]

// 先排个序，然后就可以从大到小判断，如果相邻的三个数满足三角形，那就是最大周长。 func res2(n int, a []int) int { ans := 0 sort.Ints(a) for i := n - 1; i > 2; i-- { l := a[i] + a[i-1] + a[i-2] // 周长 if a[i] < a[i-1]+a[i-2] { ans = l break } } return ans }