牛客编程巅峰赛S2第9场 - 青铜&白银&黄金 牛牛与三角形

1.对数组进行一个排序,最大的三角形必定是连在一起的,从后往前遍历,找到最大的三角形
2.最小的的通过二分来找,其中有两根肯定也是连续的,所以可以把长的两根固定 ,再通过二分缩小范围,找出最小的那根

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型一维数组 代表n个数的大小
     * @return int整型
     */
        public static int solve (int n, int[] a) {
                //先找最大 
                //排序后a<b<c<d<e  若 a c e 可以组成三角形（a+c > e），则cde一定可以组成三角形
                //题目保证一定存在可以构成三角形的三个数。 所以最大周长一定是三个连在一起的
                Arrays.sort(a);
                int max =0;
                for(int i=a.length-1; i>=2;--i){
                    if(a[i-1]+a[i-2]>a[i]){
                        max=a[i]+a[i-1]+a[i-2];
                        break;
                    }
                }
                //找最小
                // 同理 排序后 a<b<c<d<e 若a c e可以组成三角形， 则acd一定可以组成三角形
                // 所以 可以枚举中间那个值，较大的一定是中间值的下一个数
                // 较小的值可以二分
                int min =Integer.MAX_VALUE;
                for(int i=1;i<=a.length-2;++i){
                    int b = a[i];
                    int c=a[i+1];

                    int left =0;
                    int right =i;
                    while(left < right){
                        int mid = left + (right-left)/2;
                        if(a[mid]+b >c){
                            right =mid;
                        }else{
                            left= mid+1;
                        }
                    }
                    //这里要判断一下left是否重复 （left==i 的情况）
                    if(left<i && a[left]+b >c){
                        min = Math.min(min,a[left]+b+c);
                    }
                }
          }
}