A. 牛牛分蛋糕
题目形容
牛牛明天家里要来客人，所以牛牛明天特意做了他最拿手的两种蛋糕，然而他是一个有洁癖的人，所以他在分蛋糕时，有如下几个准则：
- 他不心愿一个盘子里呈现两种蛋糕
- 他心愿每个盘子中都有蛋糕
- 他想让装有起码蛋糕数量的盘子中装有的蛋糕数量尽可能多
备注:
n, a, b(1 ≤ a, b ≤ 10^5, 2 ≤ n ≤ a + b)第一个参数代表盘子的数量第二个参数代表第一种蛋糕的数量第三个参数代表第二种蛋糕的数量。程序应返回：在所有分法中，蛋糕数量起码的盘子中分到最多的蛋糕数量。示例1
输出
5, 2, 3输入
1阐明
只有一种办法把蛋糕调配到盘子里，即所有的盘子上都有一个蛋糕。示例2
输出
4, 7, 10输入
3阐明
第一个盘子中装有第一种蛋糕三个，第二个盘子中装有第一种蛋糕四个，第三个、第四个盘子中各装有第二种蛋糕五个。解法一：暴力搜盘子
思路剖析
要想装起码蛋糕数量的盘子中装的蛋糕最多，必然是平均调配蛋糕。因而能够搜寻所有的盘子调配计划，看哪种状况下平均调配到的蛋糕最多。
工夫复杂度：$O(n)$。总共有 $n - 1$ 种盘子调配计划。
空间复杂度：$O(1)$。
代码实现
public int solve (int n, int a, int b) { int res = 0; for(int i = 1; i < n; i++) { int min = Math.min(a / i, b / (n - i)); res = Math.max(res, min); } return res;}解法二：二分搜蛋糕
思路剖析
每个盘子都调配 $c$ 块蛋糕，若 $a / c + b / c \ge n$ 阐明这样调配能使 $n$ 个盘子中都有蛋糕。二分搜寻寻找最大的 $c$ 即可。
工夫复杂度：$O(log(min(a,b)))$。
空间复杂度：$O(1)$
代码实现
public int solve (int n, int a, int b) { int l = 1, r = Math.min(a, b); while(l < r){ int mid = (l + r + 1) >> 1; if(a / mid + b / mid < n) r = mid - 1; else l = mid; } return l;}B. 牛牛凑数字
题目形容
牛牛明天逛商店，看到商店里摆着一些很漂亮的数字，牛牛十分喜爱，想买一些数字带回家。
数字一共有九种类型，别离是 1 - 9 这九个数字，每个数字的价格都不一样，而且每个数字的货源都十分短缺。
牛牛是个完满主义者，他心愿用本人的可能接受的价格，从这些数字外面购买，并且凑到最大的数字带回家。
备注:
第一个参数为一个整数 n(0 ≤ n ≤ 10^6)，代表牛牛所能接受的价格。第二个参数为 1 - 9 这九个数字的价格数组，a1, a2, ……, a9(1 ≤ ai ≤ 10^5)。程序应返回:一个数字，代表牛牛能凑到的最大的数字。当然，如果牛牛一个数字都买不起，返回 "-1" 即可。留神，因为数字可能会很大，所以程序中须要解决成 string 类型进行返回。示例1
输出
5,[5,4,3,2,1,2,3,4,5]输入
"55555"阐明
第 5 个数字只须要破费 1，所以买 5 个第 5 个数字能够凑到最大值 55555。示例2
输出
2,[9,11,1,12,5,8,9,10,6]输入
"33"阐明
购买 2 个第 3 个数字，能够凑到最大值为 33。解法：贪婪
思路剖析
要想数字最大，首先得数字的数量最多。其次，在雷同数量的数字时，应尽可能买最大的数字。
如果每一个都买破费起码的数字 $a$，那么数字的数量 $cnt$ 必然是最多的。
找到这个最多的数量后，从大到小搜查数字，若不缩小数量的状况下能买到更大的数字，则用它替换掉 $a$。
工夫复杂度：$O(\frac n {min(a_i)})$。最多买 $\frac n {min(a_i)}$ 个数字，因而最多搜查这么屡次。
空间复杂度：$O(1)$。
代码实现
public String solve (int n, int[] a) { StringBuilder res = new StringBuilder(); int min = Integer.MAX_VALUE; int minNum = 0; for(int i = 0; i < 9; i++ ) { if(a[i] <= min) { min = a[i]; minNum = i + 1; } } if(n < min) return "-1"; boolean incre = true; while(incre && n > min) { incre = false; for(int i = 8; i >= minNum; i--) { if(n >= a[i] && ((n - a[i]) / min == n / min - 1)) { res.append(i + 1); n -= a[i]; incre = true; break; } } } for(int i = 1; i <= n / min; i++) res.append(minNum); return res.toString();}另一种写法(工夫复杂度没变，只是升高了代码量)
public String solve (int n, int[] a) { StringBuilder res = new StringBuilder(); int minCost = Integer.MAX_VALUE; for(int i = 0; i < 9; i++ ) minCost = Math.min(minCost, a[i]); if(n < minCost) return "-1"; int cnt = n / minCost; for(int i = 8; i >= 0 && res.length() < cnt; i--){ while(n - a[i] >= minCost * (cnt - res.length() -1)){ res.append(i + 1); n -= a[i]; if(res.length() == cnt) break; } } return res.toString();}C. 牛妹的野菜
题目形容
书接上回，牛妹组织春游，有一个乏味的我的项目是挖番薯。聪慧的牛妹拿到了一个表明了番薯洞的地图，每个番薯洞中有肯定数量的番薯。同时，咱们晓得番薯洞的连贯门路，并规定门路是单向且小序号指向大序号，也无环。能够从任意一处开始挖，而后沿着连贯往下挖（仅能抉择一条门路），当无连贯时，完结。
设计一种挖番薯的计划，使得能够挖到更多的番薯。
输入门路。
备注:
总番薯数量不超过1000000，番薯洞数量不超过250.示例1
输出
[5,10,20,5,4,5],[[1,2],[1,4],[2,4],[3,4],[4,5],[4,6],[5,6]]输入
"3-4-5-6"阐明
很显著 先去第三点拿20个番薯，再去第四个点拿5个，再去第五个点拿4个，再去第六个点拿5个。这个计划最优解法： 回溯
思路剖析
(心田 os: 作为成年人，所有番薯我全要。一条门路上的番薯只够牛妹一个人吃！)
当咱们处于洞口 $a$ 时，如果咱们晓得了每一个洞口 $b (b \in next(a))$ 的最优计划，那么能够间接比拟汇合 $next(a)$ 的各个计划，抉择其中最优的作为下一个洞口。
按照这个思路，咱们只有从门路的底部往头搜查，就能够一次遍历失去所有洞口的最优计划。那么如何找到门路的底部呢？答案就是利用回溯。从入口递归的往下搜查洞口，而后回溯中返回下一个洞口的最优计划。
工夫复杂度：$O(n)$。每个洞口最多搜查一次
空间复杂度：$O(n^2)$。对于 $n$ 个洞口，须要记录它们的下一个洞口。
代码实现
List<Integer>[] next; // 从 i 登程的下一个洞口String[] path; // 从 i 登程的最优计划门路int[] potatoMaxNum; //从 i 登程能够挖到番薯的最大数量int[] potatoNum;public String digSum (int[] potatoNum, int[][] connectRoad) { int n = potatoNum.length; next = new List[n + 1]; path = new String[n + 1]; potatoMaxNum = new int[n + 1]; this.potatoNum = potatoNum; for(int i = 1; i <= n; i++) next[i] = new ArrayList<Integer>(250); for(int[] path: connectRoad){ next[path[0]].add(path[1]); } String res = ""; int maxNum = 0; for(int i = 1; i <= n; i++) {//遍历 n 个洞口，看看哪个洞口登程失去的番薯最多 dfs(i); if(potatoMaxNum[i] > maxNum) { maxNum = potatoMaxNum[i]; res = path[i]; } } return res;}public int dfs(int d){//返回洞口 d 登程失去的最大番薯数量 if(potatoMaxNum[d] != 0) return potatoMaxNum[d]; if(next[d].isEmpty()) {//最初一个洞口了 path[d] = "" + d; return potatoMaxNum[d] = potatoNum[d - 1]; } int maxd = d; for(Integer nextd: next[d]) {//看看下一步去哪个洞口失去的番薯最多 int num = dfs(nextd); if(num > potatoMaxNum[maxd]) maxd = nextd; } potatoMaxNum[d] = potatoNum[d - 1] + potatoMaxNum[maxd]; path[d] = d + "-" + path[maxd]; return potatoMaxNum[d];}写在最初
大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请动动你的小手指点个赞????。你的反对是我创作路上的最大能源。谢谢大家！
也欢送来公众号【往西汪】找我游玩～