如何以更低时间复杂度解决任务-程序员处理计数问题

问题核心分析 #

不需要逐次模拟每个程序员处理任务的过程——这正是O(m*n)等解法超时的根本原因。问题本质是累计消耗的总工作量与任务循环周期的对应关系：

• 每一轮任务的总工作量是所有任务时长的总和 total_work
• 累计消耗工作量超过total_work时，等价于完成了整数轮任务，剩余工作量只需对应到单轮任务中的位置即可

预处理步骤 #

1. 计算任务总工作量：
   先算出所有任务的总时长 total_work = sum(tasks)。如果total_work = 0，说明所有任务初始状态已完成，直接返回长度为m的全0数组即可。
2. 构建前缀和数组：
   生成前缀和数组 prefix_sum，其中 prefix_sum[0] = 0，prefix_sum[i] = tasks[0] + tasks[1] + ... + tasks[i-1]。该数组可快速定位某一累计工作量对应的任务位置。

逐程序员处理逻辑 #

维护全局累计工作量变量 current_total = 0，对每个程序员的工作时长p执行以下步骤：

1. 更新累计工作量：current_total += p
2. 计算剩余工作量在单轮中的位置：remaining = current_total % total_work
   • 若remaining == 0：说明刚好完成整数轮任务，所有任务处于完成状态，待处理任务数为0
   • 否则：在prefix_sum数组中用二分查找找到最大索引k，使得prefix_sum[k] <= remaining。此时已完成任务数为k，待处理任务数为n - k

代码示例（Java） #

import java.util.Arrays;

public class TaskProcessing {
    public static int[] countPendingTasks(int[] tasks, int[] programmers) {
        int n = tasks.length;
        int m = programmers.length;
        int[] result = new int[m];
        
        // 计算总工作量与前缀和数组
        long totalWork = 0;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            totalWork += tasks[i];
            prefixSum[i + 1] = prefixSum[i] + tasks[i];
        }
        
        if (totalWork == 0) {
            Arrays.fill(result, 0);
            return result;
        }
        
        long currentTotal = 0;
        for (int i = 0; i < m; i++) {
            currentTotal += programmers[i];
            long remaining = currentTotal % totalWork;
            if (remaining == 0) {
                result[i] = 0;
                continue;
            }
            // 二分查找定位已完成任务数
            int left = 0, right = n;
            int completed = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (prefixSum[mid] <= remaining) {
                    completed = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            result[i] = n - completed;
        }
        
        return result;
    }
}

复杂度说明 #

• 预处理前缀和：O(n)
• 处理每个程序员：单次二分查找耗时O(log n)，m个程序员总耗时O(m log n)
• 整体时间复杂度：O(n + m log n)，完全适配n、m达2*10^5的规模

内容的提问来源于stack exchange，提问作者CodeCrusader