贪心
基于微扰证明但关系不具有传递性的贪心
感觉起了个离谱的标题
先看题：P2123 皇后游戏
既然这题像国王游戏就顺着考虑微扰贪心，对于两个大臣 \(i,j=i+1\)，假设现在的顺序是最优顺序，那么记 \(last = c_{i-1},sum = \sum_{k = 1}^{i-1} a_k\) 有:
交换 \(i,j\) 之后：
\[cost_2 = max\{last + b_j, sum + a_j + b_j, sum + a_j + a_i\} + b_i \]根据假设有：
\[cost_1 \leq cost_2 \]简单分讨一下我们发现第一项是没用的，所以可以改写上式：
\[max\{sum + a_i + b_i, sum + a_i + a_j\} + b_j\leq max\{sum + a_j + b_j, sum + a_j + a_i\} + b_i \]\(max\) 里的东西提出来，移项：
\[max\{b_i, a_j\} - a_j - b_i \leq max\{b_j, a_i\} - a_i - b_j \]两边比较对称，所以分讨一边：
\[b_i < a_j\ 时,\ 左式=-b_i \]\[b_i > a_j\ 时,\ 左式=-a_j \]所以原式化为：
\[min\{b_i,a_j\} \geq min\{b_j, a_i\} \]好的这是一个非常优美的柿子，这题到此结束。
骗你的，看一遍题目再看这个柿子，你会发现这是基于两个大臣相邻的前提下的关系，而排序要求的是任意两个元素之间的关系，换句话说，我们需要找一种具有传递性的关系，所以最终的目的是把下标一样的放在不等式的同一侧，这样就能对所有元素适用了。
好不容易推出来的柿子不能扔，再看一遍这个柿子：
\[min\{b_i,a_j\} \geq min\{b_j, a_i\} \]回到最初看这个题的时候，一种朴素的贪心思想是尽量把 \(a\) 小 \(b\) 大的放在前面，那么可以根据这个性质展开分讨：
\(a_i<b_i,a_j<b_j①\) 按 \(a\) 升序。
\(a_i=b_i,a_j=b_j②\) 这个随便排就行了，对答案没有影响。
\(a_i>b_i,a_j>b_j③\) 按 \(b\) 降序。
我们按这三种特殊情况内部排完序，考虑他们之间的顺序：① 比 ② 优，③ 比 ② 劣。
所以这题就这么解决了。