【华为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即可（单个一组，每天都看答案即可），如果只有一天，也就不用划分，返回总长度-最大值即可

3. 动态规划

定义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即可

4. 二分法
   二分模板参考：【华为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。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问出处以查看本文的最新版本。