【华为OD题库-107】编码能力提升计划-java

题目

为了提升软件编码能力，小王制定了刷题计划，他选了题库中的n道题，编号从0到n-1，并计划在m天内按照题目编号顺序刷完所有的题目(注意，小王不能用多天完成同一题)
在小王刷题计划中，小王需要用time[i]的时间完成编号i的题目此外，小王还可以查看答案，可以省去该题的做题时间。为了真正达到刷题效果，小王每天最多直接看一次答案。我们定义m天中做题时间最多的一天耗时为T(直接看答案的题目不计入做题总时间)。请你帮小王求出最小的T是多少
输入描述
第一行输入为time,time[i]的时间完成编号i的题目
第二行输入为m，m表示几天内完成所有题目，1<= m<= 180
输出描述
最小耗时整数T
示例1:
输入
999,999,999
4
输出
0
说明
在前三天中，小王每天都直接看答案，这样他可以在三天内完成所有的题目并不花任何时间
示例2:
输入
1,2,2,3,5,4,6,7,8
5
输出
4
说明
第一天完成前3题，第3题看答案；
第二天完成第4题和第5题，第5题看答案；
第三天完成第6和第7题，第7题看答案；
第四天完成第8题，直接看答案；
第五天完成第9题，直接看答案

思路

同leetcode:LCP 12. 小张刷题计划

可从三种思路解决此题

1. 回溯
   排列组合参考：【JAVA-排列组合】一个套路速解排列组合题

列举所有可能的划分方法，找到最小的T（T为每种划分方法的和的最大值）
以数据1,2,2,3,5,4,6,7,8为例，加入要划分5组，那么需要找到4个数，在其前面划上|表示划分，如：
1,2,|2,3,|5,4,|6,7,|8，元数据被划分成了5组，按照此思路，|不能出现在第一个数字，因为不能有空的分组。所以dfs从1开始。
对于每种划分方案：计算每一段的结果（该和-该段最大值），得到最大的结果作为该种划分方案的结果
最后获取每种方案最小的结果即可
还有考虑特殊情况，比如输入的天数大于等于数组总长度，那么直接返回0即可（单个一组，每天都看答案即可），如果只有一天，也就不用划分，返回总长度-最大值即可

2. 动态规划

定义dp[i][j]为选取数组的前i个数据划分为j段所能得到的最大连续子数组和减去该段最大值后的最小值。
在进行状态转移，考虑第j段的具体范围，我们可以枚举k，即前k个数分割为j-1段，而k+1到第i个数为第j段。这j段子数组和中的最大值就等于：dp[k][j-1]和sub(k+1,i)-max(k+1，i)中的较大值。其中sub(i,j)代表数组nums下标落在[i,j]范围的和，max(i,j)代表数组nums下标落在[i,j]的最大值。
由于最后要求的是最小值，所以dp可以初始化一个较大的值
上述步骤中要求dp[k][j-1]和sub(k+1,i)-max(k+1，i)中的较大值，当j=1时，会利用dp[0][0]求最大值，所以还需要给dp[0][0]赋一个较小的值，比如0。
最后返回dp[nums.length][m]即可，m为天数
同样的，需要考虑特殊情况，当输入的天数大于等于数组总长度，那么直接返回0即可

3. 二分法
   二分模板参考：【华为OD题库-046】生日礼物-java

由题可知，左边界为0（单个数据一组），右边界为sum-max（整体划分为一组）
题目需要找到满足条件的最小值，也就是找第一个满足条件的值（可直接利用二分模板）,如果满足条件则right=mid,不满足条件则left=mid+1;
关键在于checked(nums,mid,k)方法，即怎么判定对于给定mid，是否满足条件？
假设nums可以划分为5组，每一组和不大于mid，那么其一定可以划分为6组，7组…（将前5组再次划分为更细的分组，只要最大分组不超过nums的长度即可），最后每组和也不大于mid。所以该方法的判定逻辑为：
遍历nums，如果累加和超过了mid，那么就需要新开分组，最后统计能够划分的分组数，如果得到的分组数不超过mid，那么就满足条件。

方法3的效率优于方法1和2

题解

1. 回溯

package hwod;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class CodeImprovePlan {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int day = sc.nextInt();System.out.println(codeImprovePlan(nums, day));}private static int res = Integer.MAX_VALUE;private static int cnt;private static int codeImprovePlan(int[] nums, int day) {int size = nums.length;if (size <= day) return 0;if (day == 1) {int sum = 0, max = 0;for (int k = 0; k < nums.length; k++) {sum += nums[k];max = Math.max(nums[k], max);}return sum - max;}cnt = day-1;//划分day段，那么就是找day-1个数，在其前面划短杠表示分段LinkedList<Integer> path = new LinkedList<>();dfs(nums, 1, path);return res;}private static void dfs(int[] nums, int start, LinkedList<Integer> path) {if (path.size() == cnt) {ArrayList<Integer> list = new ArrayList<>(path);int curMax = 0;//基于当前分段得到的最大值int left, right;for (int i = 0; i <= list.size(); i++) {if (i == list.size()) {left = list.get(i - 1);right = nums.length;} else {right = list.get(i);left = i == 0 ? 0 : list.get(i - 1);}int maxTmp = 0, sumTmp = 0; //某段的最大值和累计和for (int k = left; k <right ; k++) {sumTmp += nums[k];maxTmp = Math.max(nums[k], maxTmp);}curMax = Math.max(curMax, sumTmp - maxTmp);}res = Math.min(curMax, res);return;}for (int i = start; i < nums.length; i++) {path.addLast(i);dfs(nums, i + 1, path);path.removeLast();}}
}

2. 动态规划

package hwod;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class CodeImprovePlan {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int day = sc.nextInt();System.out.println(codeImprovePlan(nums, day));}//动态规划private static int codeImprovePlan(int[] nums, int day) {int size = nums.length;if(day>=size) return 0;int[][] dp = new int[size + 1][day + 1];for (int i = 0; i < size + 1; i++) {Arrays.fill(dp[i], Integer.MAX_VALUE);}dp[0][0] = 1;int[] sub = new int[size + 1];for (int i = 0; i < nums.length; i++) {sub[i + 1] = sub[i] + nums[i];}for (int i = 1; i < size+1; i++) {for (int j = 1; j < day+1; j++) {for (int k = 0; k < i; k++) {dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k] - getMax(nums, k-1, i-1)));}}}return dp[size][day];}private static int getMax(int[] nums, int start, int end) {start = Math.max(0, start);int res = 0;for (int i = start;  i<=end; i++) {res = Math.max(nums[i], res);}return res;}
}

3. 二分法

package hwod;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class CodeImprovePlan {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int day = sc.nextInt();System.out.println(codeImprovePlan(nums, day));}//二分法private static int codeImprovePlan(int[] nums, int day) {int left = 0, right = 0, sum = 0, max = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];max = Math.max(max, nums[i]);}right = sum - max;while (left < right) {int mid = left + (right - left >> 1);if (checked(nums, mid, day)) {right = mid;} else {left = mid + 1;}}return left;}private static boolean checked(int[] nums, int mid, int day) {int cnt = 0, sum = 0, max = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];max = Math.max(nums[i], max);if (sum - max > mid) {cnt++;sum = nums[i];max = nums[i];}}return cnt + 1 <= day;//+1：加上最后一段未统计的分组}
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。

说明

本专栏所有文章均为原创，欢迎转载，请注明文章出处：https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问出处以查看本文的最新版本。