先把这个推导看完
现在我们来讲一下总结
首先，我们要观察到\(c_i\)递增，这样才能更简单
然后，这道题目教会了我们如果去掉max中的max（或min中的min）：先把所有的项全部移到外层的max里面去，再把内层max消掉就可以只剩下一个max了
那么为什么这道题目能够消掉\(y+b_i+b_j\)呢？其实就像题解里面说的，数学上是肯定错误的，但是对于这类题目（注意是这类题目，不是这道题目，至于这类是哪一类，看完下面的解释就知道了）是都可以消去的
我们考虑最终的⑤式，如果我们最终的序列满足⑤式，那么肯定是可以推导到①式上面的那一个式子的，那么对这个式子，我们给两个max里面都加上\(y+b_i+b_j\)，肯定也是成立的，而这就是我们最开始推导的那一个式子
就是说，我们按照这种排序规则排序后，最开始的式子就能够被推导出来，就不会出现交换相邻两项出现更优的情况
所以以后遇到这种题，尽管有max（或min），里面有相同项都先消掉再说
然后我们根据这个式子排序（注意cmp函数里面不要加等于号，stl的排序都不要加）后模拟即可
但是，有一个很自然的问题：最终的排序一定是最优的吗？
就是说，最优排序一定满足这个条件，但是满足这个条件的一定是最优排序吗？
答案是否定的
比如下面：
7 3
1 1
1 6
然而还有一种排序也满足条件：
1 1
1 6
7 3
但是前者算出来17，后者算出来12
怎么解决？
首先明白一个定理：任何一个序列都可以通过有限次邻项交换变成任何另一个序列
我们这个时候回到国王游戏这一道题目
这一道题目按照\(a_i \times b_i ≤ a_{i+1} \times b_{i+1}\)排序，那么中间会存在一些乘积相等的数（就是这个序列被分成了若干个块，每个块之间的乘积严格递增，但是块内的乘积相等），那么最优答案不可能会在块之间进行交换，因为答案会变差（当然最优序列也必须满足以上条件，就是说如果想通过交换邻项去得到更优的情况，一定是在块内交换的），然而在块内交换，由于乘积都相等，每一次交换答案都不变，所以我们任意找一个满足条件的序列就可以了
我们思考一下上面的排序有何特殊的地方：每一个关键字都只跟自身元素有关，而不是像⑤式一样跟前后两项都有关
就是说，如果关键字只跟自身有关，那么排序后关键字肯定就具有传递性，在同一块内任意交换，由于具有传递性，就会导致答案不变，所以任何一个序列都满足题目
那么回到皇后游戏，我们要想办法把⑤式变成只跟自身有关的式子，由于只跟自身有关系，所以我们按照每个大臣\(a\)和\(b\)的大小进行讨论
一旦当我们按照上述方法排序后，这个序列是满足⑤式的，而且每个块中（一共有三个组，每个组里面有若干个块）任意交换都不会改变答案
比如在第一组内，交换\(i\)和\(i+1\)，其中\(a_i=a_{i+1}\)
设\(d=max(c_{i-1},\sum_{j=1}^{i} a_j)\)
交换前：因为\(d≥\sum_{j=1}^{i} a_j,b_i＞a_i\)，则有\(max(d+b_i,\sum_{j=1}^{i} a_j + a_{i+1})+b_{i+1}=d+b_i+b_{i+1}\)
交换后：因为\(b_{i+1}＞a_{i+1}=a_i\)，则有\(max(d+b_{i+1},\sum_{j=1}^{i} a_j + a_{i+1})+b_{i}=d+b_i+b_{i+1}\)
所以前后不变