洛谷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;
}