B4156 [厦门小学生 C++ 2023] 太空旅行

· · 题解

本题是运筹学的经典模型——流水线调度作业模型的 Johnson 不等式的运用。其他的常见模型可参考 运营管理学习笔记-第十章。

Johnson 不等式是 S. M. Johnson 在 1954 年提出的用于解决两台机器流水车间调度问题以最小化最大完工时间的最优算法。它是一种贪心算法，步骤如下：

  1. 将所有 N 架飞船分成两个集合。集合 S_1 包含所有满足 U(i) \le V(i) 的飞船 i。集合 S_2 包含所有满足 U(i) > V(i) 的飞船 i。
  2. 对集合 S_1 中的飞船，按照它们的 U(i) 值进行非递减 (升序) 排序。对集合 S_2 中的飞船，按照它们的 V(i) 值进行非递增 (降序) 排序。
  3. 最终的最优处理顺序是先按照排序后的顺序处理 S_1 中的所有飞船，然后紧接着按照排序后的顺序处理 S_2 中的所有飞船。

这也就是其他题解中所写的：U 值小的尽量往前放，V 值大的尽量往后放。如果 U \le V，就看 U 值，越小越靠前；如果 U > V，就看 V 值，越大越靠后。这样进行排序统计答案，即可通过本题。

这样做确实能完成本题。但是我不认为这个贪心是非常直观显然的。而这一个贪心的证明也并不简单，甚至可以说是十分繁琐。证明 Johnson 不等式可以使用邻项交换法完成。下面给出一个简要证明。

假设存在一个飞船处理序列 \pi，其不完全符合 Johnson 不等式，也即存在一对相邻的飞船 (i,j)，它们的顺序不符合 Johnson 不等式。我们需要证明的是，将 (i,j) 交换可以让总花费时间不增加的同时，其符合 Johnson 不等式的排序思路，成为最优方案。为方便叙述，我们定义 C_{k,1}(\pi) 表示在一个飞船处理序列 \pi 中，第 k 艘飞船到达火星的时间，C_{k,2}(\pi) 表示第 k 艘飞船到达天王星的时间。

假设 i 是序列中第 k 个元素，那么，原本不交换的飞船处理序列是 \pi=(\pi_1,\pi_2,\dots,\pi_{k-1},i,j,\pi_{k+2},\dots,\pi_N)，而交换后的序列是 \pi'=(\pi_1,\pi_2,\dots,\pi_{k-1},j,i,\pi_{k+2},\dots,\pi_N)。实际上我们只需要比较的是 C_{k+1,2}(\pi) 和 C_{k+1,2}(\pi') 的大小，因为之后的元素不会再产生差异。接下来，为了表述方便，我们简记 A=C_{k-1,1}(\pi)，即第 k-1 艘飞船到达火星的时间，以及 B=C_{k-1,2}(\pi)，即第 k-1 艘飞船到达天王星的时间。根据这些定义和变量，我们可以得出以下的几个数值：

对于飞船处理序列 \pi，我们有：

代入上述数值可以得出：C_{k+1,2}(\pi) = \max(A + U(i) + U(j), \max(A + U(i), B) + V(i)) + V(j)；

对于飞船处理序列 \pi'，类似地我们有：

代入上述数值可以得出：C_{k+1,2}(\pi') = \max(A + U(j) + U(i), \max(A + U(j), B) + V(j)) + V(i)

下面我们证明：如果飞船 i 在飞船 j 之前，但它们满足 \min(U(i), V(j)) > \min(U(j), V(i))，那么将它们的顺序交换为 (j, i)，至少不会增加第 k+1 个位置飞船的完工时间。

根据 \max 函数的运算性质：\max(x,y)+z=\max(x+z,y+z)，展开表达式可得：

由于 C_{k+1, 2}(\pi) 和 C_{k+1, 2}(\pi') 的 \max 函数中都含有 B+V(i)+V(j)，我们可以忽略它，而只在意 \max 函数的前两项。具体地，我们设 T_1=A+U(i)+U(j)+V(j)，T_2=A+U(i)+V(i)+V(j)。对应地，T_1'=A+U(j)+U(i)+V(i)，T_2'=A+U(j)+V(j)+V(i)。此时我们有：

由于 \min(U(i), V(j)) > \min(U(j), V(i))，我们可以进行分类讨论，讨论获取 U(i),U(j),V(i),V(j) 的大小关系：

由于两个序列中第三个项完全相同，所以可得：

C_{k+1,2}(\pi') = \max\{T'_1,\,T'_2,\,B+V(i)+V(j)\} \le \max\{T_1,\,T_2,\,B+V(i)+V(j)\} = C_{k+1,2}(\pi)

也即排序方式成立。因此，通过逐步交换所有违反 Johnson 不等式的相邻对 (i,j)，调整得到最优的飞船处理序列 \pi，计算该序列所需的时间，即为答案。

接下来从编写代码的角度出发，如果直接根据 \min(U(i), V(j)) \leq \min(U(j), V(i)) 编写排序的方式是错误的。在这一篇 题解 里面说的非常清楚明白。总而言之，使用本文开头所讲述的方式：

  1. 将所有 N 架飞船分成两个集合。集合 S_1 包含所有满足 U(i) \le V(i) 的飞船 i。集合 S_2 包含所有满足 U(i) > V(i) 的飞船 i。
  2. 对集合 S_1 中的飞船，按照它们的 U(i) 值进行非递减 (升序) 排序。对集合 S_2 中的飞船，按照它们的 V(i) 值进行非递增 (降序) 排序。

即可完成对飞船的排序，从而计算得出结论。从证明贪心方式到错误的排序，都体现出本题难度很高，并非部分用户所认为的只有黄题难度。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector <pair<int, int >> s(n);
    for (int i = 0; i<n; i++)
        cin >> s[i].first >> s[i].second;
    vector <pair<int, int >> g1, g2;
    for (int i = 0; i<n; i++) {
        if (s[i].first <= s[i].second)
            g1.push_back(s[i]);
        else
            g2.push_back(s[i]);
    }
    sort(g1.begin(), g1.end(), [](auto a, auto b) {
        return a.first<b.first;
    });
    sort(g2.begin(), g2.end(), [](auto a, auto b) {
        return a.second>b.second;
    });
    vector <pair<int, int >> ans;
    for (auto s: g1)
        ans.push_back(s);
    for (auto s: g2)
        ans.push_back(s);
    long long t1 = 0, t2 = 0;
    for (auto s: ans) {
        t1 += s.first;
        t2 = max(t1, t2) + s.second;
    }
    cout << t2 << endl;
    return 0;
}