牛客巅峰赛初级场题解合集（11.17）

第一场（11.17）

A、最小差值

暴力解法:

public int minDifference (int[] a) {
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < a.length-1; i++){
            for(int j = i+1; j < a.length; j++){
                res = Math.min(res,Math.abs(a[j]-a[i]));
            }
        }
        return res;
    }

先排序，再比较

public int minDifference (int[] a) {
        Arrays.sort(a);
        int res = Integer.MAX_VALUE;
        for(int i=1;i<a.length;++i){
            if(a[i]-a[i-1] >=0){
                res = Math.min(res,a[i]-a[i-1]);
            }
        }
        return res;
    }

B、TreeIV

题目分析： 观察所形成的完全二叉树，我们不难发现，此时全部结点构成了一个公差为1的等差数列。但是由于每一层的深度都不一样，所以我们把它转化为每一层的等差数列进行求解。

形成的完全二叉树，我们可以观察到每一层的最左边的结点是全是偶数，最右边的结点全是奇数，所以就有了计算每一层等差数列的起点和终点的公式。

等差数列法

private long mod = 998244353;
    public long tree4 (long n) {
        // 第一层的起点和终点都是1
        long left = 1;
        long right = 1;
        long res = 0;
        //每次i为每一层的深度，每次循环i+1，循环终点为到达最后一层
        for(int i = 1; left <= n; i++){
            //此处的目的是为了避免到最后一层时，因为要是没满的话，终点则为n
            right = Math.min(right,n);
            //等差数列的求和公式
            res += (right-left+1)*(left+right)/2%mod * i%mod;
            //下一层的起点
            left = left*2;
            //下一层的终点
            right = right*2 + 1;
        }
        return res%mod;
    }

C、牛牛组数

题目分析：

因为要将字符串分为k个数，然后使得k个数加起来的结果最大。

假设有道题是将它分为n个数(n为字符串的长度)，这样就是把它分没一个只有一个字符的数，要怎么样才能使得它最大呢？我想很简单的就能够想到就是，我们把大的数放在高位，这样结果肯定是最大的。

所以我们回到这道题，题目是要分为k个数，这k个数是随机的，并不一定等于字符串的长度，所以我们可以组成一个极大数，保证极大数的字符都是最大的，然后加上k-1个只有一个字符的并且比较小的数，极大数中的字符就按照刚刚举的例子，大的放高位，这样组成的数字加起来不就最大了嘛！(可能有点绕口，但是多想几遍相信就能够想通)

public String Maxsumforknumers (String x, int k) {
        //先转化为字符数组
        char[] c = x.toCharArray();
        //排序
        Arrays.sort(c);
        StringBuffer sb = new StringBuffer();
        //保证第k个数是最大的(后面的k-1个数为较小的数)
        //大的放高位，所有循环起点为数组的终点,然后依次循环到k-1
        for(int i = x.length()-1; i >= k-1; i--){
            //用sb拼接起来
            sb.append(c[i]);
        }
        //将sb转化为整数
        BigInteger bi = new BigInteger(sb.toString());
        //后面的k-1个个位数
        for(int i = 0; i < k-1; i++){
            //全部数字相加
            bi = bi.add(BigInteger.valueOf(c[i]-'0'));
        }
        //最后返回结果转化为字符串
        return bi.toString();
    }