牛客编程巅峰赛S2第9场 - 钻石&王者 做题记录

t1 : 正确版解法 NlogN

    public 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);
            }
        }
        return max-min;
    }

t2 dp打表找规律可得 n==2^x-1时，为奇数，否则为偶数。
然后判断n是否是 【2的幂-1】就行了。。。
java可以用BigInteger

    public boolean judge (String nn) {
        BigInteger n = new BigInteger(nn);
        BigInteger zero = new BigInteger("0");
        BigInteger one = new BigInteger("1");
        BigInteger two = new BigInteger("2");

        n=n.add(one);
        while(n.mod(two) .compareTo(zero) ==0) {
            n = n.divide(two);
        }
        return n.compareTo(one) == 0;
    }

t3:我不配...