牛客编程巅峰赛S1第4场 - 黄金&钻石

A. 牛牛分蛋糕

解题思路:二分
这道题我写了一个二分的思路，这个问题是具有二段性的，就是二分出蛋糕最少的那个盘子中的蛋糕数最多为多少，然后让所有剩余的盘子的蛋糕数都为这个数字，判断是否可以，如果可以则收缩左边界。

参考代码1

import java.util.*;


public class Solution {
    /**
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    boolean check(int v, int a, int b, int n){
         return a / v + b / v >= n;
    }

    public int solve (int n, int a, int b) {
        // write code here

        int r = Math.max(a, b);
        int l = 1;

        while(l < r){
            int mid = l + r + 1>> 1;
            if(!check(mid, a, b, n)) r = mid - 1;
            else l = mid;
        }

        return l;
    }
}

解题思路2: 枚举
可以发现，最终一定会是a的蛋糕给几个盘子，b的蛋糕给几个盘子，所以我们可以枚举a蛋糕分配的盘子数和b蛋糕分配的盘子数，找到一个使得最少蛋糕的盘子的蛋糕最多的分配方案即可。

参考代码2

import java.util.*;


public class Solution {
    /**
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    public int solve (int n, int a, int b) {
        // write code here
        int ans = 1;

        for(int i=1; i<n; i++){
            int one = a / i;
            int two = b / (n - i);

            ans = Math.max(ans, Math.min(one, two));
        }

        return ans;
    }
}

B.牛牛凑数字

解题思路
这道题是使用贪心的思路，觉得遇到这种拼接数字使得数字最大的问题，应该是这样来贪才对，就是先要保证长度最长，然后剩余的钱买更大的数字来对前面的一些数字进行替换，这样得到的数字才是最大的，在这道题中，也就是先用给定的钱买价值最小的且数字最大的数字，保证长度最长，然后用剩下的钱从当前形成的字符串的首端开始，用某个可以买起的最大的数字来对当前数字进行替换就好了。

需要注意的是，java的话要使用StringBuilder，因为String拼接字符串的速度巨慢！！

参考代码

import java.util.*;


public class Solution {
    /**
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型一维数组 1-9这九个数字的价格数组
     * @return string字符串
     */
    public String solve (int n, int[] a) {
        // write code here
        int min = 0x3f3f3f3f;
        int k = -1; // 代表价值最小的数字是几

        for(int i=0; i<9; i++) {
            if(a[i] <= min) {
                min = a[i];
                k = i + 1;
            }
        }

        if(n < min) return  "-1";
        int max_len = n / min; // 获取结果的最大长度
        int left = n % min; // 获取剩余的钱数

        char[] res = new char[max_len];
        char c = (char)(k + (int)'0');
        Arrays.fill(res, c);

        int idx = 0; // 指针
        while(left != 0) {
            left += min;

            boolean flag = false;
            for(int i=8; i>=0; i--) {
                if(left >= a[i]) {
                    res[idx] = (char)((i + 1) + (int)'0');
                    flag = true;
                    left -= a[i];
                    break;
                }
            }

            idx ++;
            if(idx == max_len || !flag) break;
        }

        StringBuffer s = new StringBuffer();
        for(int i=0; i<max_len; i++) s.append(res[i]);

        return s.toString();
    }
}

C.牛妹的野菜

解题思路
由于这张图是一张拓扑图，且要求最大，故自然而然想到DP，这里我们定义dp[i]表示以i为起点的获得番薯的最大值，状态转移方程为dp[i] = max(dp[u] + w[i]),这里u指i的所有子节点，另外需要注意这道题要输出方案，所以使用一个next数组记录每一个节点是由哪一个点转移过来的就可以了。

参考代码

import java.util.*;


public class Solution {
    int N = 310, M = N * N;
    int[] dp = new int[N]; // 表示以某个点作为起点的最大收益
    int[] next = new int[N]; // 保存每一个番薯洞穴的下一个位置
    int[] h = new int[N];
    int[] e = new int[M];
    int[] ne = new int[M];
    int[] w = new int[M];
    int idx;

    void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    int dfs(int u, int[] w){
        if(dp[u] != -1) return dp[u];

        dp[u] = w[u - 1];
        for(int i=h[u]; i!=-1; i=ne[i]){
            int j = e[i];

            dfs(j, w);

            if(dp[j] + w[u - 1] > dp[u]){
                next[u] = j;
                dp[u] = dp[j] + w[u - 1];
            }
        }

        return dp[u];
    } 

    public String digSum (int[] potatoNum, int[][] connectRoad) {
        // write code here

        Arrays.fill(dp, -1);
        Arrays.fill(next, -1);

        int n = potatoNum.length;

        Arrays.fill(h, -1);

        for(int[] cur : connectRoad) {
            add(cur[0], cur[1], potatoNum[cur[1] - 1]);
        }

        for(int i=1; i<=n; i++) dfs(i, potatoNum);

        int idx = 1;
        for(int i=1; i<=n; i++){
            if(dp[i] > dp[idx]){
                idx =  i;
            }
        }

        String res = "";
        while(idx != -1){
            if(next[idx] != -1) res += idx + "-";
            else res += idx;
            idx = next[idx];
        }

        return res;
    }
}