洛谷P1248 加工生产调度题解

题意：

某工厂收到了 \(n\) 个产品的订单，这 \(n\) 个产品分别在 A,B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 \(i\) 在 A、B 两车间加工的时间分别为 \(A_i,B_i\)。怎样安排这 \(n\) 个产品的加工顺序，才能使总的加工时间最短。

这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。

输入格式：

第一行仅—个整数 \(n\)，表示产品的数量。

接下来一行 \(n\) 个整数是表示这 \(n\) 个产品在 A 车间加工各自所要的时间。

最后的 \(n\) 个整数是表示这 \(n\) 个产品在 B 车间加工各自所要的时间。

输出格式：

第一行一个整数，表示最少的加工时间。

第二行是一种最小加工时间的加工顺序。

数据范围：

\(1\leq n\leq 10^5\)

贪心的常见套路似乎就是找到两个存在极小差异的决策，分析哪个更优，以归纳法获得最优决策。

考虑只有两个元素 \((a_1,b_1),(a_2,b_2)\) 时，设 \((a_1,b_1)\) 先处理更优。

先处理 \(1\) 再处理 \(2\) 的花费，所需时间即为最后加工完 \(2\) 所需的时间 \[ a_1 + \max\{b_1,a_2\} + b_2 \] 先处理 \(2\) 再处理 \(1\) 的花费，所需时间即为最后加工完 \(1\) 所需的时间 \[ a_2 + \max\{b_2,a_1\} + b_1 \] 根据假设可知 \[ a_1 + \max\{b_1,a_2\} + b_2 < a_2 + \max\{b_2,a_1\} + b_1 \] 移项得 \[ \max\{b_1,a_2\} - b_1 - a_2< \max\{b_2,a_1\} - a_1 - b_2 \] 可以发现不等式左右较大的项均被抵消掉了，则 \[ - \min \{b_1,a_2\} < - \min \{b_2, a_1\} \] 即 \(\min \{b_2, a_1\}<\min \{b_1,a_2\}\) 。这个东西是有传递性的，但是我们不能直接排序。

原因在于 C++ 标准库要求用于排序的运算符必须满足严格弱序。

什么是严格弱序呢？

对于一个比较运算符 \(<\) ，记 \(\not<\) 为不满足该运算符，若满足以下四个条件，则称该运算符是严格弱序的。

\(x \not< x\) （非自反性）
若 \(x < y\) ，则 \(y \not< x\) （非对称性）
若 \(x < y, ~y < z\) ，则 \(x < z\) （传递性）
若 \(x \not< y,~y \not< x, ~y\not< z,~z\not< y\) ，则 \(x \not< z, z \not< x\) （不可比性的传递性）

而我们刚刚的排序并不满足不可比性的传递性。

也就是说刚刚的排序有（记 \(a \downarrow b\) 为 \(\min\{a,b\}\) ） \[ (a_x\downarrow b_y)= (b_x \downarrow a_y) \land (a_y \downarrow b_z) = (b_y \downarrow a_z) \nRightarrow (a_x\downarrow b_z) = (b_x \downarrow a_z) \] 因此我们需要找到一个具有「不可比性的传递性」的式子。

分析一下刚刚的排序条件，可以发现这个和 \(a,b\) 的大小有关。

\(a_1 < b_1 \land a_2 < b_2\) 时，按 \(a_1 < a_2\) 排序。
\(a_1 = b_1\land a_2 = b_2\) 时，排序结果无影响。
\(a_1 > b_1 \land a_2 > b_2\) 时，按 \(b_1 > b_2\) 排序。

可以发现这三种情况对应了 \(a_i - b_i < 0,~a_i - b_i = 0,~a_i - b_i > 0\)

因此我们将每个元素，第一维按 \(\mathrm{sgn}(a_i - b_i)\) 排序，第二维按对应的排序方式排序，即可得到答案。

等有时间再研究研究这个严格弱序的东西，咕咕咕。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define sgn(x) (((x) > 0) - ((x) < 0))
#define N ((int)(1e5+15))

int n,c1,c2,a[N],b[N],d[N],o[N];
bool cmp(int x,int y)
{
    if(d[x] != d[y]) return d[x] < d[y];
    return (d[x] <= 0) ? (a[x] < a[y]) : (b[x] > b[y]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1; i<=n && (o[i] = i); i++) d[i] = sgn(a[i] - b[i]);
    sort(o + 1, o + 1 + n, cmp);
    c1 = a[o[1]]; c2 = a[o[1]] + b[o[1]];
    for(int i=2; i<=n; i++)
    { c2 = max(c1 + a[o[i]], c2) + b[o[i]]; c1 += a[o[i]]; }
    cout << c2 << '\n';
    for(int i=1; i<=n; i++) cout << o[i] << " \n"[i==n];
    return 0;
}