P1248 加工生产调度 - Johnson 法则如何使用 - java版

题目：P1248 加工生产调度【经典 Johnson 两机调度问题】【贪心】

理解一下题：图解

前导

推导排序规则：

min(x.a , y.b) < min(y.a , x.b); 

但是这个题的比较函数有一个取min的操作，这个会导致：不满足不可比性的传递性。

不可比性的传递性

• 不可比性传递：如果𝑢与𝑣不可比（相等），且𝑣与𝑤不可比，那么𝑢与𝑤也一定不可比，即若u = v，v = w，则u = w。
• 当两个比较结果相等（即不可比）时，这种相等关系不具有传递性：即x与y不可比，y与z不可比，但x与z却可能可比。这正是破坏了不可比性的传递性。
• 举个例子x、y、z，如图
  
• 判断逻辑如下：
  

虽然不懂，但是记住😅。好像又懂了。

我的问题：对于当min(x.a, y.b) = min(x.b, y.a) 且 min(y.a, z.b) = min(y.b, z.a) 时，min(x.a, z.b) = min(x.b, z.a) 不一定成立，这六个min规则中，最后两个的内容和前面四个是完全不一样的，为什么要看是否满足不可比性的传递性？

解答：上面这个推理实际上说的是，当x排在y前，y排在z前时，x不一定排在z前，这是它的实际意义。但实际上，对于不可比性的传递性，应该满足如果x排在y前，y排在z前，那么x应该排在z前，因此根据实际意义来看，还是需要满足不可比性的传递性的。

如何解决不可比性的传递性？—— Johnson 法则

Johnson 法则

直接推翻之前的流程（上面的不等式不能完全通过hack数据），改用新模板：

• 题解 / Johnson算法的模板
• 流水调度问题-动态规划-Johnson法则-两种方法

Johnson 法则是解决双机流水车间调度问题（即每个工件先在 A 机加工，再到 B 机加工，目标是最小化总完工时间）的最优排序算法。其核心思想是将工件分为两类，并分别按特定顺序排列，从而保证整体顺序最优。

使用法二实现该算法：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] q = new int[n + 1];//暂存第一行数组aArrayList<int[]> a = new ArrayList<>();//a,b,iArrayList<int[]> b = new ArrayList<>();//a,b,ifor(int i = 1;i <= n;i++) q[i] =sc.nextInt();for(int i = 1;i <= n;i++) {int[] t = new int[3];//a,b,it[0] = q[i];t[1] = sc.nextInt();t[2] = i;if(t[0] < t[1]) a.add(t);else b.add(t);}Collections.sort(a, (x, y)-> Integer.compare(x[0], y[0]));//a，升序Collections.sort(b, (x, y)-> Integer.compare(y[1], x[1]));//b，降序a.addAll(b);//合并列表int suma = 0, sumb = 0;for(int i = 0;i < n;i++) {suma += a.get(i)[0];sumb = Math.max(suma, sumb) + a.get(i)[1];}System.out.println(sumb);for(int[] t : a) {System.out.print(t[2] + " ");}}
}