编码能力提升计划 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

为了提升软件编码能力，小王制定了刷题计划，他选了题库中的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题，直接看答案

题解

题目分析

本题属于典型的二分查找 + 贪心算法问题。

题目要求我们在 m 天内完成 n 道题，每天最多看一次答案，目的是求出使得每天耗时的最小值 T。为了达到这个目标，我们需要尽可能均匀地分配题目到 m 天内，并保证每一天的耗时不超过一个给定的上限 T。

通过题意，我们可以使用二分法来找到这个最小值 T。对于给定的 T 值，我们通过贪心策略判断是否能够在 m 天内完成所有题目。如果可以完成，说明 T 可能过大，继续尝试更小的 T；如果不能完成，说明 T 过小，需要增大 T。

解题思路

1. 二分查找范围确定：
   • 最小值 left 初始化为 -1，表示没有刷题的时间。
   • 最大值 right 为所有题目耗时的总和，因为如果没有看答案的机会，那么一天内耗时的最大值不可能超过所有题目的耗时总和。
2. 二分查找逻辑：
   • 每次二分时，选择中间值 mid 作为当前假设的最大耗时 T。
   • 然后调用贪心算法 can_complete_in_days(T, time, m)，来判断在 m 天内，是否可以完成所有题目。
3. 贪心策略：
   • 每天从题目序列中开始做题，记录当天最大题目时间 max_time，用来表示今天最多看答案的一题。
   • 如果当天完成这道题后的总耗时 total_time + 当前题目耗时 - max_time 不超过当前假设的最大时间 T，则继续累加当天的耗时，否则新开一天。
   • 最后，判断 m 天内是否能完成题目。
4. 终止条件：
   • 当 left + 1 == right 时，二分查找结束，right 即为答案。

Java

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] time = Arrays.stream(sc.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();
        int m = sc.nextInt();

        int left = -1, right = IntStream.of(time).sum();

        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (canCompleteInDays(mid, time, m))