小张刷题计划

LCP 12. 小张刷题计划

为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。

在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。

示例 1：

输入：time = [1,2,3,3], m = 2

输出：3

解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。

示例 2：

输入：time = [999,999,999], m = 4

输出：0

解释：在前三天中，小张每天求助小杨一次，这样他可以在三天内完成所有的题目并不花任何时间。

限制：

1 <= time.length <= 10^5
1 <= time[i] <= 10000
1 <= m <= 1000

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minTime(vector<int>& time, int m) { } };

golang 解法, 执行用时: 44 ms, 内存消耗: 8.1 MB, 提交时间: 2023-09-13 23:46:30

//T越大，m越小，反之亦然
//找出最小的T，使得m最大
func getM(time []int, t int) int {
    days := 1
    sum := 0
    max := 0
    request := true
    for i := 0; i < len(time); i++ {
        if max < time[i] {
            max = time[i]
        }
        sum += time[i]
        if sum > t {
            if request {
            sum -= max
            request = false
            } else {
                days++
                request = true
                max = 0
                sum = 0
                i--
            }
        }
    }
    return days
}

func minTime(time []int, m int) int {
    //T最小为0，最大为sum
    sum := 0
    for i := 0; i < len(time); i++ {
        sum += time[i]
    }
    left, right := 0, sum
    for left < right {
        mid := left + (right - left) >> 1
        days := getM(time, mid)
        if days > m {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

golang 解法, 执行用时: 40 ms, 内存消耗: 8.2 MB, 提交时间: 2023-09-13 23:37:40

func minTime(time []int, m int) int {
    l, r := 0, 0
    for _, t := range time {
        r += t
    }
    
    for l < r {
        mid := (l+r)>>1
        if check(mid, time, m) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

func check(limit int, cost []int, day int) bool {
    use_day, total_time, max_time := 1, 0, cost[0]
    for _, i := range cost[1:] {
        if total_time + min(max_time, i) <= limit {
            total_time, max_time = total_time + min(max_time, i), max(max_time, i)
        } else {
            use_day++
            total_time, max_time = 0, i
        }
    }
    return use_day <= day
}

func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }

java 解法, 执行用时: 9 ms, 内存消耗: 54.4 MB, 提交时间: 2023-09-13 23:30:32

class Solution {
    public int minTime(int[] time, int m) {
        int n = time.length;
        if(m >= n)  return 0; // 每天都使用求助机会
        // 二分查找上界：一天刷完所有题目，并对耗时最长的那题使用求助 // sum - max
        int upper = 999_999_999; // 10^5 * 10000 - 1

        // 二分查找下界(前提 m < n): 简便起见直接定义0
        int lower = 0;
        while(lower <= upper){
            int mid = (lower + upper) >>> 1;
            if(canFinish(time, mid, m)){
                upper = mid - 1; // 希望更小的T
            }else{
                lower = mid + 1; // 先确保可以完成
            }      
        }
        return lower;
    }

    // limit 每天的最大耗时 m 计划的天数
    private boolean canFinish(int[] time, int limit, int m){
        int day = 1, elapse =0;
        int max = time[0];
        int n = time.length;
        // 我做题的最初想法：一开始先不考虑求助，进行简单的累加
        // 超过limit 先别慌，试着把 当前最大的那个 干掉，继续看下一个数字 
        // 如果下一个数字(记作t) 比 之前的最大值 还大，试一下 干掉新的最大值，之前的最大值 救活
            // 假如不更换 求助的题目，这一天做题时间是 增加 t, 但 求助 t时间的这道题目更加划算 
            // 所以在更换了求助的题目后，做题时间可以【少】增加 t-max
            // 因此 为了做这题 实际增加的时间是  t - (t-max) = max // 前提 t > max
        // 如果 t <= max, 不需要更换求助的题目，做题增加的时间 就是 t
        
        // 对上述思路稍加改进：【先假设第一个直接求助，如果后续有更值得求助的，就更换求助的题目】 这样代码更简洁些
        for(int i=1; i<n; i++){
            int t = time[i];
            // int delta = t > max ? max : t; // t - (t-max) if t > max
            int delta = Math.min(t, max); // 新增的时间
            elapse += delta; // 试错法,先假设可以做出这道题
            if(elapse > limit){ // 当前这题 这一天做不出了 此时将 这题 先假设为后一天的求助机会
                day++;
                elapse = 0;
                max = t;
            }else{ // 这道题能做
                max = Math.max(max, t); // 更新max
            }
        }
        return day <= m;
    }
}

cpp 解法, 执行用时: 92 ms, 内存消耗: 54.8 MB, 提交时间: 2023-09-13 23:29:50

class Solution {
public:
    bool Check(int limit, vector<int> cost, int day) {
      // 每组划分 limit 的最大和，贪心划分看有多少组
        int useday, totaltime, maxtime;
        useday = 1; totaltime = maxtime = 0;
        for (int i=0; i<cost.size(); ++i) {
            int nexttime = min(maxtime, cost[i]);
            if (nexttime + totaltime <= limit) {
                totaltime += nexttime;
                maxtime = max(maxtime, cost[i]);
            } else {
                ++useday;
                totaltime = 0;
                maxtime = cost[i];
            }
        }
        return (useday <= day);
    }
    int minTime(vector<int>& time, int m) {
        int left, right, middle;
        left = right = 0;
        for (int i=0; i<time.size(); ++i) {
            right += time[i];
        }
        while (left <= right) {
            middle = (left + right) >> 1;
            if (Check(middle, time, m)) right = middle - 1;
            else left = middle + 1;
        }
        return left;
    }
};

python3 解法, 执行用时: 1980 ms, 内存消耗: 26.9 MB, 提交时间: 2023-09-13 23:29:23

'''
给定一个数组，将其划分成 M 份，使得每份元素之和最大值最小，每份可以任意减去其中一个元素。
'''
class Solution:
    def minTime(self, time: List[int], m: int) -> int:
        l,r = 0,sum(time)
        while l<r:
            mid = (l+r)>>1
            if self.check(mid,time,m):
                r = mid
            else:
                l = mid + 1
        return l

    def check(self, limit, cost, day):
        use_day,total_time,max_time = 1,0,cost[0]
        for i in cost[1:]:
            if total_time+min(max_time,i)<= limit:
                total_time,max_time = total_time+min(max_time,i),max(max_time,i)
            else:
                use_day += 1
                total_time,max_time = 0,i
        return use_day<=day

上一题

下一题

详情