写作业 - 题解

标签与难度

标签: 枚举, 模拟, 排程问题, 贪心, 细节题难度: 1600

题目大意喵~

有两个好朋友 A 和 B，他们都要完成数学和语文两科作业，真是辛苦呢，喵~

我们知道他们每个人独立完成每项作业需要的时间：

同学 A：数学要 $a_1$ 分钟，语文要 $b_1$ 分钟。
同学 B：数学要 $a_2$ 分钟，语文要 $b_2$ 分钟。

为了快点写完去玩，他们可以“借鉴”对方已经完成的作业。如果一个人已经写完了某科作业，另一个人再写这科作业时，只需要花原来一半的时间，也就是 $t/2$ 的时间。

不过，他们有个小小的原则：一旦开始独立写某项作业，就必须写完，不能中途改成借鉴别人的。也就是说，对于任何一项作业，你要么从头到g尾独立完成，要么就等对方写完，然后拿来借鉴。

我们的任务就是，帮他们找到一个最棒的合作方案，让他们俩都完成所有作业所花费的总时间最短，喵~

解题思路分析

喵哈~ 这道题看起来像是一个小小的排程问题！我们要找的是一个最优的策略，让最后的完成时间（也就是跑得慢的那个同学的完成时间）尽可能早。因为状态不多（两个人，两份作业），我们可以把所有可能的高效合作策略都想一遍，然后取其中最快的一种，这就是枚举法的威力所在，喵！

让我来带你分析一下都有哪些可行的策略吧！

我们用 $T_{total}$ 表示总的完成时间。这个时间取决于最后完成作业的那个同学是什么时候完成的。

策略一：各做各的，互不干扰

这是最简单直接的策略啦。A 同学埋头做自己的，B 同学也埋头做自己的。他们俩同时开始。

A 同学完成所有作业需要的时间是 $T_A = a_1 + b_1$ 。
B 同学完成所有作业需要的时间是 $T_B = a_2 + b_2$ 。

因为他们是同时开始的，所以总时间就是他们中较慢的那一个人的时间。

T_{strategy1} = \max(a_1 + b_1, a_2 + b_2)

策略二：分工合作，交叉借鉴

这可是个很聪明的策略哦！一个人负责一科，另一个人负责另一科，完成第一轮后，再互相借鉴对方的成果。这样两个人都只用独立完成一科作业，效率大大提升！

这里有两种分工方案：

方案 2a: A 做数学，B 做语文

第一阶段: A 开始独立做数学（耗时 $a_1$ ），同时 B 开始独立做语文（耗时 $b_2$ ）。这个阶段在 max(a1, b2) 分钟后结束，此时 A 的数学和 B 的语文都完成了。
第二阶段: 现在他们可以互相借鉴了！A 开始借鉴 B 的语文（耗时 $b_1/2$ ），同时 B 开始借鉴 A 的数学（耗时 $a_2/2$ ）。这个阶段在 max(b1/2, a2/2) 分钟后结束。

所以，这个方案的总时间就是两个阶段的时间之和：

T_{strategy2a} = \max(a_1, b_2) + \max(b_1/2, a_2/2)

方案 2b: A 做语文，B 做数学

同理，我们只要交换一下角色就可以啦~

T_{strategy2b} = \max(b_1, a_2) + \max(a_1/2, b_2/2)

策略三：一人主导，一人跟随

这种策略是，一个同学当“学霸”，按顺序完成自己的两份作业。另一个同学当“小跟班”，在这位学霸完成一科后，就立刻开始借鉴这一科。

听起来有点复杂？别怕，我们画个时间轴就清楚了，喵~

方案 3a: A 先做数学再做语文，B 全程跟随

A 的时间线:
- 时间 0 到 a1: A 独立完成数学。
- 时间 a1 到 a1 + b1: A 独立完成语文。
- A 在 a1 + b1 时刻完成所有作业。
B 的时间线:
- 在 t = a1 时刻，A 的数学作业好了！B 立刻开始借鉴数学，需要 a2/2 时间。
- 在 t = a1 + b1 时刻，A 的语文作业好了！B 可以开始借鉴语文了，需要 b2/2 时间。
- B 必须完成借鉴数学和借鉴语文这两件事。B 不能同时做两件事，所以他需要安排一个顺序。
- B 在 t=a1 时刻解锁了数学任务，在 t=a1+b1 时刻解锁了语文任务。
- B 的最优选择是：在 t=a1 时马上开始借鉴数学。这项任务会持续到 a1 + a2/2。当 A 在 a1+b1 完成语文时，B 可能还在忙着借鉴数学（如果 a2/2 > b1），也可能已经闲下来了（如果 a2/2 <= b1）。
- B 开始借鉴语文的时间点，必须同时满足两个条件：1. A的语文写完了 (t >= a1+b1)；2. B自己有空了（即借鉴数学的任务完成了，t >= a1+a2/2）。所以 B 最早能在 max(a1+b1, a1+a2/2) 时刻开始借鉴语文。
- B 的最终完成时间 = (B开始借鉴语文的时间) + (借鉴语文所需时间) = max(a1 + b1, a1 + a2/2) + b2/2。
- 这个式子可以化简一下，变成 a1 + max(b1, a2/2) + b2/2。
- 总时间是 A 和 B 中较慢的那个，而 B 的完成时间 a1 + max(b1, a2/2) + b2/2 肯定不会比 A 的 a1+b1 早。所以总时间就是 B 的完成时间。

所以，这个方案的总时间是：

T_{strategy3a} = a_1 + \max(b_1, a_2/2) + b_2/2

通过对称分析，我们可以得到其他三种“一人主导”的方案：

方案 3b: A 先做语文再做数学，B 全程跟随
$T_{strategy3b} = b_1 + \max(a_1, b_2/2) + a_2/2$
方案 3c: B 先做数学再做语文，A 全程跟随
$T_{strategy3c} = a_2 + \max(b_2, a_1/2) + b_1/2$
方案 3d: B 先做语文再做数学，A 全程跟随
$T_{strategy3d} = b_2 + \max(a_2, b_1/2) + a_1/2$

总结

好啦，我们已经分析出了所有核心的、可能的优化策略！总共有 1 + 2 + 4 = 7 种。我们只要把这7种情况的时间都算出来，然后取一个最小值，就是最终的答案啦！是不是很简单呢，喵~

代码实现

下面是我根据上面的思路，为你精心准备的 C++ 代码哦~ 变量名都取得很清楚，还加了详细的注释，希望能帮到你，呐！

cpp

#include <iostream>
#include <algorithm>
#include <vector>

// 使用 long long 防止中间计算溢出，是个好习惯喵~
using ll = long long;

// a1, b1 是 A 的数学和语文时间
// a2, b2 是 B 的数学和语文时间
void solve() {
    ll a1, b1, a2, b2;
    std::cin >> a1 >> b1 >> a2 >> b2;

    // 用一个向量来存放所有可能策略的时间
    std::vector<ll> possible_times;

    // --- 策略一：各做各的 ---
    // A 和 B 独立完成所有作业，总时间是较慢的那个人的时间
    possible_times.push_back(std::max(a1 + b1, a2 + b2));

    // --- 策略二：分工合作 ---
    // 方案 2a: A 做数学, B 做语文, 然后交叉借鉴
    possible_times.push_back(std::max(a1, b2) + std::max(b1 / 2, a2 / 2));
    // 方案 2b: A 做语文, B 做数学, 然后交叉借鉴
    possible_times.push_back(std::max(b1, a2) + std::max(a1 / 2, b2 / 2));

    // --- 策略三：一人主导，一人跟随 ---
    // 方案 3a: A 先数学后语文, B 跟随
    possible_times.push_back(a1 + std::max(b1, a2 / 2) + b2 / 2);
    // 方案 3b: A 先语文后数学, B 跟随
    possible_times.push_back(b1 + std::max(a1, b2 / 2) + a2 / 2);
    // 方案 3c: B 先数学后语文, A 跟随
    possible_times.push_back(a2 + std::max(b2, a1 / 2) + b1 / 2);
    // 方案 3d: B 先语文后数学, A 跟随
    possible_times.push_back(b2 + std::max(a2, b1 / 2) + a1 / 2);

    // 从所有策略中找出最优解 (最小时间)
    ll min_time = possible_times[0];
    for (size_t i = 1; i < possible_times.size(); ++i) {
        if (possible_times[i] < min_time) {
            min_time = possible_times[i];
        }
    }

    std::cout << min_time << std::endl;
}

int main() {
    // 处理多组测试数据
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(1)$ 对于每一组输入数据，我们都只执行了固定次数的算术运算和比较。所以计算一个答案的时间是常数级别的，喵~ 如果有 $T$ 组测试数据，总时间复杂度就是 $O(T)$ 。
空间复杂度: $O(1)$ 我们只用了几个变量来存储输入和计算结果，没有使用大小随输入规模变化的额外空间，所以空间复杂度是常数级别的。

知识点总结

这道题的核心是分类讨论和枚举。面对一个看似复杂的调度问题，不要慌张，可以尝试把它分解成几种基本的、有代表性的策略。

模型简化: 将实际问题（写作业）抽象成一个调度模型，明确了任务、参与者和规则。
策略枚举: 识别出所有有竞争力的基本策略（完全独立、分工合作、一人主导）。这是解题的关键，需要清晰的逻辑思维来避免遗漏或重复。
时间线分析: 对于涉及先后顺序和依赖关系的策略（比如“一人主导”策略），通过模拟时间线的推进，可以准确地计算出总耗时，特别是处理好等待（max函数的应用）和并行的情况。

通过这道题，我们可以学到，解决某些最优化问题不一定需要高深的算法，有时候，清晰的逻辑分析和全面的情况枚举也是一种非常有效的方法！要相信自己的分析能力哦，喵~

写作业 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

策略一：各做各的，互不干扰 ​

策略二：分工合作，交叉借鉴 ​

策略三：一人主导，一人跟随 ​

总结 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​