C. Schedule Management - 题解

喵~ 主人 sama，欢迎来到我的题解小屋！今天我们要解决的是一个关于任务分配的有趣问题呢。别担心，只要跟着我的思路走，再复杂的问题也会变得像毛线球一样好解开的，喵~

比赛与标签

比赛: Educational Codeforces Round 131 (Rated for Div. 2) 标签: binary search, greedy, implementation, two pointers 难度: *1400

题目大意喵~

我们有 n 个勤劳的工人喵和 m 个任务要完成。每个任务都有一个指定的“专家”工人，专家做起来超快，只要 1 小时！如果让不是专家的工人来做，就要花 2 小时呢，效率会低一些的说。

工人们可以同时开工，但每个人一次只能做一个任务。我们的目标是，合理安排所有任务，让最后一名工人完工的时间尽可能的早！我们要找的就是这个最早的完工时间，喵~

简单来说，就是求一个最小的时间 T，使得我们能在这个时间内把所有 m 个任务都做完。

解题思路详解

主人 sama，一看到“求最小值”，你有没有闻到一股熟悉的味道呀？没错！就是二分答案的味道！

为什么可以用二分答案呢？我们可以想一下：如果所有任务能在 T 小时内完成，那么在 T+1 小时内肯定也能完成，对吧？（因为时间更充裕了嘛）。反之，如果 T 小时内完不成，那么在 T-1 小时内也肯定完不成。

这种答案具有的单调性，正是使用二分答案的完美信号！我们可以二分枚举最终的完成时间 T，然后写一个 check(T) 函数来判断，在 T 小时内是否能完成所有任务。

接下来就是最关键的部分：如何实现 check(T) 函数呢？

在一个给定的时间 T 内，我们当然希望工人们尽可能高效地工作。最贪心的想法就是：

优先让专家做自己的任务：因为专家做只需要 1 小时，别人做要 2 小时，这显然是最划算的。
专家做不完的，再找帮手：如果一个专家工人 i 的任务太多了，在 T 小时内都做不完，那多出来的任务就只能拜托其他有空闲时间的工人来帮忙了。

基于这个贪心策略，我们来分析一下每个工人在 T 小时内的状况：

首先，我们用一个 counts 数组统计出每个工人 i 擅长的任务数量 counts[i]。

对于每个工人 i：

情况一：任务太多，忙不过来！ (counts[i] > T) 这个工人是个大忙人！他有 counts[i] 个擅长的任务，但在 T 小时内，他最多只能完成 T 个。那么，剩下的 counts[i] - T 个任务就变成了“待救援任务”，需要别人来帮忙。我们把所有工人的“待救援任务”数量加起来，记作 needed_help。
情况二：做完本职工作，还有空闲！ (counts[i] <= T) 这个工人很能干，他会在 counts[i] 小时内完成所有自己擅长的任务。之后，他还剩下 T - counts[i] 小时的空闲时间。这些时间可以用来帮助其他忙不过来的工人。因为帮助别人做一个任务需要 2 小时，所以他能帮忙完成 (T - counts[i]) / 2 个任务。我们把所有工人能提供的“帮助量”加起来，记作 can_help。

最后，我们只需要比较 can_help 和 needed_help 的大小：

如果 can_help >= needed_help，说明所有空闲的工人提供的帮助足以完成所有待救援的任务。太棒了！这说明时间 T 是可行的。我们就可以尝试一个更小的时间，所以让二分的 high = T - 1。
如果 can_help < needed_help，说明人手不够，时间 T 内无法完成所有任务。我们需要更多的时间，所以让二分的 low = T + 1。

二分的上下界怎么定呢？时间最小是 1，最大嘛... 假设最坏的情况，一个工人要做所有 m 个任务，而且都不是他擅长的，那就要 2 * m 小时。所以二分范围设为 [1, 2 * m] 就很安全啦！

就这样，通过不断地二分缩小范围，我们最终就能找到那个最小的可行时间 T 啦，喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n, m;
    std::cin >> n >> m;
    // counts[i] 用来记录工人 i 擅长的任务数量
    std::vector<int> counts(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int task_worker_id;
        std::cin >> task_worker_id;
        counts[task_worker_id]++;
    }

    // 二分答案的范围，low 是下界，high 是上界
    // 最坏情况是一个工人做所有m个非擅长任务，需要 2*m 时间
    long long low = 1, high = 2LL * m, ans = 2LL * m;

    while (low <= high) {
        long long mid = low + (high - low) / 2; // mid 就是我们尝试的时间 T
        
        long long needed_help = 0; // 需要被帮助完成的任务总数
        long long can_help = 0;    // 空闲工人能提供的帮助任务总数

        for (int i = 1; i <= n; ++i) {
            if (counts[i] > mid) {
                // 工人 i 的任务太多了，在 mid 时间内做不完
                // 多出来的 counts[i] - mid 个任务需要别人帮忙
                needed_help += counts[i] - mid;
            } else {
                // 工人 i 在 mid 时间内能做完自己的任务
                // 剩下的 mid - counts[i] 小时可以去帮忙
                // 帮忙做一个任务需要2小时，所以能帮 (mid - counts[i]) / 2 个
                can_help += (mid - counts[i]) / 2;
            }
        }

        if (can_help >= needed_help) {
            // 如果能提供的帮助 >= 需要的帮助，说明时间 mid 是可行的
            // 记录下这个可行的答案，并尝试更小的时间
            ans = mid;
            high = mid - 1;
        } else {
            // 帮助不够，说明时间 mid 太短了，需要更多时间
            low = mid + 1;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: O(N * log M) 的说。我们的二分查找会在 [1, 2*m] 的范围内进行，所以二分部分的复杂度是 O(log M)。在每次二分检查 check(T) 时，我们都需要遍历一遍 n 个工人来计算 needed_help 和 can_help，这部分的复杂度是 O(N)。所以总的时间复杂度就是 O(N * log M) 啦！
空间复杂度: O(N) 的说。我们主要用了一个 counts 数组来存储每个工人擅长的任务数，它的大小和工人数量 n 成正比。所以空间复杂度就是 O(N) 呐~

知识点与总结

主人 sama，这次的解题之旅是不是收获满满呀？我们来总结一下关键点吧！

二分答案 (Binary Search on Answer)：这是解决“求最小/最大可能值”这类问题的强大武器！当你发现问题的答案具有单调性时，就可以大胆地将求解问题转化为判定问题。
贪心策略 (Greedy Strategy)：在 check 函数中，我们采用了贪心的思想——优先让专家做自己的任务。这个局部最优的选择（1小时 vs 2小时）最终导向了全局的判断，是解决问题的核心逻辑之一。
问题转换: 我们把一个复杂的“调度优化问题”成功转换成了一个简单的“判定问题”（在时间 T 内是否能完成），这是一种非常重要的解题思维！

希望这篇题解能帮到主人 sama 呐！只要找到问题的单调性，二分答案就是我们手中的一把利剑！继续加油，期待在下一道题解中再见到你喵~ ❤️

C. Schedule Management - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路详解 ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​