笔记汇总

加工生产调度

首先，按照常规的贪心做法。考虑两个产品 $i,j$。如果按照 $i,j$ 的顺序，那么有两种情况，我们分别画图解释：

1. $A_j <= B_i$

1. $A_j > B_i$
   

汇总一下，总时间为 $A_i + max(A_j, B_i) + B_j = 总和 - min(A_j, B_i)$

用临项交换法可知，$min(A_i, B_j) <= min(A_j, B_i)$ 的关系排序即可，由于 $min$ 是不可比性传递，最好将 $B$ 作为第二关键字，以免出错。

排序完后，$A$时间短的往前塞，$B$则往后塞。

然后再去找等到 $A$ 车间加工完: $t[i]$,或等到 $B$ 车间加工完: $sum$。再取其中最大值。

皇后游戏

容易发现，排序为 $min(A_i, B_j) <= min(A_j, B_i)$ 的关系，但由于这是不可比性传递，

直接排序不满足严格弱序，还要加一维关键字，

观察 $a$ 的前缀和对答案有一定的影响，把 $a$ 更小的放前面是更优的，所以将 $a$ 作为第二关键字。

Difficult Mountain

把所有登山者分成两类，一类是 $a_i <= s_i$ 的记为集合 $S$，一类是 $s_i < a_i$ 的记为集合 $T$，前者内部互不干扰，后者可以按照 $a_i$ 从小到大贪心。观察 $S$ 对 $T$ 的影响，对于 $i 属于 S, j 属于 T$，若 $s_j < a_i <= s_i < a_j$，那么 $i, j$ 之间只能选一个，因为 $a_i < a_j$ 所以选 $i$ 更优，其它情况下可以证明 $i, j$ 可以同时选择。

以 $max(a_i, s_i)$ 为第一关键字，$s_i$ 为第二关键字贪心即可。

证明技巧

打一个暴力程序，正解需要满足：

1. 严格弱序
2. 排序完成后任意交换相邻元素均不会使答案更优。

邻项交换

在可以通过比较相邻两项得出交换或不交换一定不会更差时，可以通过邻项交换排序的方式来得到最优解。

邻项交换排序的比较函数需要满足严格弱序，并且排序完成后任意交换相邻元素都不会更优。

使用这种算法时，一定要注意以上两点，才能得到真正正确的算法。