北京工商网站,海南百度推广公司有哪些,花都网站推广,wordpress链接跳转页面题目 为了提升软件编码能力#xff0c;小王制定了刷题计划#xff0c;他选了题库中的n道题#xff0c;编号从0到n-1#xff0c;并计划在m天内按照题目编号顺序刷完所有的题目(注意#xff0c;小王不能用多天完成同一题) 在小王刷题计划中#xff0c;小王需要用time[i]的时…题目 为了提升软件编码能力小王制定了刷题计划他选了题库中的n道题编号从0到n-1并计划在m天内按照题目编号顺序刷完所有的题目(注意小王不能用多天完成同一题) 在小王刷题计划中小王需要用time[i]的时间完成编号i的题目此外小王还可以查看答案可以省去该题的做题时间。为了真正达到刷题效果小王每天最多直接看一次答案。我们定义m天中做题时间最多的一天耗时为T(直接看答案的题目不计入做题总时间)。请你帮小王求出最小的T是多少 输入描述 第一行输入为time,time[i]的时间完成编号i的题目 第二行输入为mm表示几天内完成所有题目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. 小张刷题计划 可从三种思路解决此题
回溯 排列组合参考【JAVA-排列组合】一个套路速解排列组合题 列举所有可能的划分方法找到最小的TT为每种划分方法的和的最大值 以数据1,2,2,3,5,4,6,7,8为例加入要划分5组那么需要找到4个数在其前面划上|表示划分如 1,2,|2,3,|5,4,|6,7,|8元数据被划分成了5组按照此思路|不能出现在第一个数字因为不能有空的分组。所以dfs从1开始。 对于每种划分方案计算每一段的结果该和-该段最大值得到最大的结果作为该种划分方案的结果 最后获取每种方案最小的结果即可 还有考虑特殊情况比如输入的天数大于等于数组总长度那么直接返回0即可单个一组每天都看答案即可如果只有一天也就不用划分返回总长度-最大值即可 动态规划 定义dp[i][j]为选取数组的前i个数据划分为j段所能得到的最大连续子数组和减去该段最大值后的最小值。 在进行状态转移考虑第j段的具体范围我们可以枚举k即前k个数分割为j-1段而k1到第i个数为第j段。这j段子数组和中的最大值就等于dp[k][j-1]和sub(k1,i)-max(k1i)中的较大值。其中sub(i,j)代表数组nums下标落在[i,j]范围的和max(i,j)代表数组nums下标落在[i,j]的最大值。 由于最后要求的是最小值所以dp可以初始化一个较大的值 上述步骤中要求dp[k][j-1]和sub(k1,i)-max(k1i)中的较大值当j1时会利用dp[0][0]求最大值所以还需要给dp[0][0]赋一个较小的值比如0。 最后返回dp[nums.length][m]即可m为天数 同样的需要考虑特殊情况当输入的天数大于等于数组总长度那么直接返回0即可 二分法 二分模板参考【华为OD题库-046】生日礼物-java 由题可知左边界为0单个数据一组右边界为sum-max整体划分为一组 题目需要找到满足条件的最小值也就是找第一个满足条件的值可直接利用二分模板,如果满足条件则rightmid,不满足条件则leftmid1; 关键在于checked(nums,mid,k)方法即怎么判定对于给定mid是否满足条件 假设nums可以划分为5组每一组和不大于mid那么其一定可以划分为6组7组…将前5组再次划分为更细的分组只要最大分组不超过nums的长度即可最后每组和也不大于mid。所以该方法的判定逻辑为 遍历nums如果累加和超过了mid那么就需要新开分组最后统计能够划分的分组数如果得到的分组数不超过mid那么就满足条件。 方法3的效率优于方法1和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 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个数在其前面划短杠表示分段LinkedListInteger path new LinkedList();dfs(nums, 1, path);return res;}private static void dfs(int[] nums, int start, LinkedListInteger path) {if (path.size() cnt) {ArrayListInteger 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();}}
}
动态规划
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(daysize) 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 size1; i) {for (int j 1; j day1; 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; iend; i) {res Math.max(nums[i], res);}return res;}
}
二分法
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。百度和各类采集站皆不可信搜索请谨慎鉴别。技术类文章一般都有时效性本人习惯不定期对自己的博文进行修正和更新因此请访问出处以查看本文的最新版本。
