之前一直都丢在luogu，现在终于放这了
n个东西需要加工，在A加工的时间是ai, 在B加工的时间是bi,每个东西必须在A加工完后才能在B加工，求最少时间
贪心大体思路：不要让A有空闲时间，B的空闲时间尽量少是最优的
对于贪心思路采用归纳法
对于n = 1的情况，显然最少时间是a1 + b1
对于n = 2的情况：
第一种情况：
假设生产顺序是先(a1, b1)再(a2, b2)：
如果b2加工前最后是在等待a2，也就是b1<a2，所以Tmin = a1 + a2 + b2
如果b2加工前最后是在等b1,也就是b1>a2，那么Tmin = a1 + b1 + b2
则容易看出Tmin = a1 + b1 + a2 + b2 - min(b1, a2)
第二种情况：
假设生产顺序是(a2,b2)再(a1,b1)，同理可得Tmin = a1 + b1 + a2 + b2 - min(b2, a1)
综上，Tmin = a1 + b1 + a2 + b2 - max(min(b1, a2), min(b2, a1))
则可以得到Johnson不等式：
对于两个待加工的东西x, y，排序
min(x1, y2) < min(x2, y1)
会使得最终答案最优
其实就是，对于所有待加工的东西所花时间(a, b)分成p1类别a <= b和p2类别a > b，对于p1按a递增排序，对于p2按b递减排序，先执行第一种，再执行p2种，得到的答案一定最优
Johnson不等式和这个贪心思路为什么得到的顺序一定相同呢？
对于(a1, b1)和(a2, b2)，假设a1 <= b1属于p1类别，a2 > b2属于第二类别
因为Johnson不等式有min(a1, b2) < min(a2, b1)，无论左边的是a1小还是b2小，都一定小于右边的min(a2, b1)，所以能够得到上面的思路
标签：min,加工,调度,证明,a1,a2,b1,b2,流水 From： https://www.cnblogs.com/blueparrot/p/17812336.html