问题描述：
有n根棍子,棍子i的长度为ai,从中选出三根棍子组成周长和最大的三角形
* 若能组成成三角形则输出最大周长,若不能输出0
* 样例输入:
* n = 5
* a = {2,3,4,5,10};
* 输出:
* 12(3+4+5)
思路：
原书中给出的思路就是暴力枚举，也是大家直接能想到的思路，枚举所有木棍的组合始终保留周长最长的结果，最后即为所求 复杂度O(n ^3)
贪心策略的核心思想：将所给木棍的长度排序(O(nlgn))，从最长的开始遍历，每次只看紧次于该木棍的两根木棍能否组成三角形，若能则为结果，若不能向下枚举则。最大的周长结果一定为紧次于该木棍长的两根木棍,若仅次于最长边的边都不能组成三角形,则数组中没有能和该边长组成三角形的 向下重复遍历-----简而言之 排好序后,一个边长只需要比较一次 且倒序寻找,率先找到的一定是三角形周长和最大的。
java代码实现如下
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int res = maxPerimeter2(a, n);
System.out.println(res + " " + maxPerimeter1(a, n));
}
/**
* 贪心策略:
* 复杂度O(nlgn)-快排
* @param a
* @param n
* @return
*/
private static int maxPerimeter2(int[] arr, int n) {
Arrays.sort(arr);
int ans = 0;
for(int i = n - 1; i >= 2; i--) {//到最后三个比较一次结束
int a = i;int b = i - 1;int c = i - 2;
if(check(a, b, c, arr)) {
ans = arr[a] + arr[b] + arr[c];
break;
}
}
return ans;
}
/**
* 暴力枚举:枚举出所有可能组成三角形的情况
* O(n^3)
* 选出最大的*-*
* @param a
* @param n
* @return
*/
private static int maxPerimeter1(int[] a, int n) {
int ans = 0;//最终结果
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; k++) {
if(check(i, j, k, a)) {
int c = a[i]+a[j]+a[k];
if(c > ans) ans = c;
}
}
}
}
return ans;
}
/**
* 检测两边之和是否大于第三边
* @param i
* @param j
* @param k
* @return
*/
private static boolean check(int a, int b, int c, int[] arr) {
if(arr[a]+arr[b] > arr[c]&&arr[b]+
arr[c] > arr[a]&&arr[c]+arr[a] > arr[b])
return true;
return false;
}
}
网友评论