2026-11-02：统计每个班次结束后的未完成任务数。用go语言，给定两个整数数组 tasks 和 shifts。tasks 中每个元素表示对应任务需要消耗的

2026-11-02：统计每个班次结束后的未完成任务数。用go语言，给定两个整数数组 tasks 和 shifts。tasks 中每个元素表示对应任务需要消耗的时间；shifts 中每个元素表示对应班次可提供的工作时间。所有任务只能按照给定先后顺序依次处理。如果某个班次结束时当前任务还没有做完，那么下一个班次会从该任务已经完成的位置继续处理，而不是重新开始该任务。如果某个班次内把所有任务都完成了，则该班次立即结束，剩余时间作废，后续班次会从第一个任务重新开始处理。所谓未完成任务，是指尚未被完整处理完的任务，正在处理但还没有结束的任务也计入未完成。需要返回 ans，其中 ans[j] 表示第 j 个班次结束后仍未完成的任务数量。

1 <= tasks.length <= 100000。

1 <= shifts.length <= 100000。

1 <= tasks[i] <= 1000000000。

1 <= shifts[i] <= 1000000000。

输入： tasks = [1,4,4], shifts = [9,1,4]。

输出： [0,2,1]。

解释：

班次 0：所有任务需要 1 + 4 + 4 = 9 单位时间，因此全部完成。未完成任务数量为 0。

班次 1：重新从任务 0 开始处理。该班次有 1 单位时间，因此任务 0 完成。未完成任务数量为 2。

班次 2：从任务 1 的当前位置继续处理。该班次有 4 单位时间，因此任务 1 完成。未完成任务数量为 1。

题目来自力扣4012。

详细过程如下：

1. 设任务数量为n，即tasks的长度。

2. 将tasks原地转换为前缀和数组：

• 转换后，tasks[i]表示前i+1个任务的总耗时。

• 例如原任务为[1,4,4]，转换后为[1,5,9]。

• 这样tasks[n-1]就是所有任务的总耗时。

• 由于每个任务耗时都是正数，所以前缀和数组严格递增，适合二分查找。

3. 初始化累计时间变量t = 0：

•t表示从本轮第一个任务开始，到当前班次结束为止累计处理的工作时间。

• 如果还没有完成所有任务，t会持续累计到后续班次。

• 如果某一班次完成了所有任务，t会被重置为 0，表示下一班次从第一个任务重新开始。

4. 按顺序遍历每一个班次shift：

• 把当前班次可提供的时间加到累计时间中，即t增加当前shift。

• 此时t表示从本轮开始到当前班次结束，总共已经消耗的工作时间。

5. 判断所有任务是否已经完成：

• 如果t大于或等于所有任务总耗时，即t >= tasks[n-1]，说明当前班次结束时所有任务已经完成。

• 按题意，如果班次内完成了所有任务，该班次立即结束，剩余时间作废，后续班次从第一个任务重新开始。

• 因此把t重置为 0。

• 当前班次结束后的未完成任务数为 0，所以把当前班次对应的结果写成 0。

6. 如果所有任务还没有完成：

• 需要在已经变成前缀和的tasks数组中，用二分查找找到第一个总耗时大于t的位置。

• 代码中查找的是第一个大于等于t+1的位置，因为所有耗时都是整数，这等价于找第一个前缀和大于t的任务位置。

• 设找到的位置为pos。

•pos的含义是：前pos个任务已经完整完成，因为前pos个任务的总耗时都不超过当前累计时间t。

• 从第pos个任务开始，后面的任务还没有完整完成。注意，第pos个任务可能正在处理但尚未完成，按题意也要计入未完成。

• 因此当前班次结束后的未完成任务数量为n - pos。

• 把这个数量写入当前班次对应的结果位置。

7. 继续处理下一个班次：

• 如果前面没有完成所有任务，t保持累计值，不重置，表示下一班次继续从当前未完成任务的位置往后处理。

• 如果前面完成了所有任务，t已经重置为 0，下一班次从第一个任务重新开始。

8. 遍历结束后，shifts数组已经被原地覆盖为每个班次结束后的未完成任务数量，直接返回即可。

以示例tasks = [1,4,4]，shifts = [9,1,4]为例：

• 先把tasks转换为前缀和：[1,5,9]，总耗时为 9。

• 第 0 个班次时间为 9：

• 累计时间t = 0 + 9 = 9。

• 9 大于等于总耗时 9，说明所有任务完成。

• 未完成数为 0。

•t重置为 0。

• 第 1 个班次时间为 1：

• 累计时间t = 0 + 1 = 1。

• 1 小于总耗时 9。

• 在前缀和[1,5,9]中找第一个大于 1 的位置，得到位置 1。

• 说明前 1 个任务已经完成，剩下3 - 1 = 2个任务未完成。

• 结果为 2。

• 第 2 个班次时间为 4：

• 累计时间t = 1 + 4 = 5。

• 5 小于总耗时 9。

• 在前缀和[1,5,9]中找第一个大于 5 的位置，得到位置 2。

• 说明前 2 个任务已经完成，剩下3 - 2 = 1个任务未完成。

• 结果为 1。

• 最终结果为[0,2,1]。

复杂度分析：

• 总时间复杂度：
前缀和计算需要遍历tasks一次，时间复杂度为O(n)。
每个班次需要进行一次二分查找，二分查找时间复杂度为O(log n)。
设shifts长度为m，则总时间复杂度为O(n + m log n)。

• 总额外空间复杂度：
算法原地修改tasks为前缀和数组，并原地覆盖shifts作为结果数组。
除少量变量外，二分查找为迭代实现，不需要额外数组。
因此总额外空间复杂度为O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "sort"
)

 func countTasks(tasks, shifts []int) []int {
    n := len(tasks)
    // 原地计算 tasks 的前缀和
    for i := 1; i < n; i++ {
        tasks[i] += tasks[i-1]
    }

     t := 0
    for i, shift := range shifts {
        t += shift
        if t >= tasks[n-1] { // 完成所有任务
            t = 0
            shifts[i] = 0
        } else {
            shifts[i] = n - sort.SearchInts(tasks, t+1)
        }
    }
    return shifts
}

 func main() {
    tasks := []int{1, 4, 4}
    shifts := []int{9, 1, 4}
    result := countTasks(tasks, shifts)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import bisect

 def count_tasks(tasks, shifts):
    n = len(tasks)

     # 原地计算 tasks 的前缀和
    for i in range(1, n):
        tasks[i] += tasks[i - 1]

     t = 0
    for i, shift in enumerate(shifts):
        t += shift

         if t >= tasks[-1]:  # 完成所有任务
            t = 0
            shifts[i] = 0
        else:
            idx = bisect.bisect_left(tasks, t + 1)
            shifts[i] = n - idx

     return shifts

 def main():
    tasks = [1, 4, 4]
    shifts = [9, 1, 4]

     result = count_tasks(tasks, shifts)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  


 using namespace std;

 vector countTasks(vector tasks, vector shifts) {
    int n = tasks.size();

     // 原地计算 tasks 的前缀和
    for (int i = 1; i < n; i++) {
        tasks[i] += tasks[i - 1];
    }

     int t = 0;
    for (int i = 0; i < (int)shifts.size(); i++) {
        t += shifts[i];

         if (t >= tasks[n - 1]) { // 完成所有任务
            t = 0;
            shifts[i] = 0;
        } else {
            // 第一个 > t 的位置，等价于 Go 的 sort.SearchInts(tasks, t+1)
            int idx = upper_bound(tasks.begin(), tasks.end(), t) - tasks.begin();
            shifts[i] = n - idx;
        }
    }
    return shifts;
}

 int main() {
    vector tasks = {1, 4, 4};
    vector shifts = {9, 1, 4};

     vector result = countTasks(tasks, shifts);

     cout << "[";
    for (int i = 0; i < (int)result.size(); i++) {
        if (i > 0) cout << ", ";
        cout << result[i];
    }
    cout << "]" << endl;

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。