皇后游戏

参考/推荐：题解 P2123 【皇后游戏】 确实是一道值得深入思考的好问题！！！ 背景既然提示了和国王游戏有关系，并且显然也是一个排序的贪心题目。 也一定是用微扰法（交换临项法）寻找并证明。 不妨设，前面的一个人是i，后面一个人是i+1 i前面的一个人的c值为p,i前面的人的a总和是sum 那么，我们现在要找到i在i+1前面的条件。 ①i在i+1前面： 贡献： $max(max(p,sum+a_i)+b_i,sum+a_i+a_{i+1})+b_{i+1}$ 化简一下就是： $max(p+b_i+b_{i+1},sum+a_i+b_i+b_{i+1},sum+a_i+a_{i+1}+b_{i+1})$ ②同理，i+1在i前面 化简以后是： $max(p+b_i+b_{i+1},sum+a_{i+1}+b_i+b_{i+1},sum+a_i+a_{i+1}+b_i)$ 我们现在要探究①小于②的条件 发现，共同有的是：$p+b_i+b_{i+1}$ 这一项可以两边直接消掉。最终不会影响排序的结果。 那么就是比较： $max(sum+a_i+b_i+b_{i+1},sum+a_i+a_{i+1}+b_{i+1})$ 和 $max(sum+a_{i+1}+b_i+b_{i+1},sum+a_i+a_{i+1}+b_i)$ 去掉sum，再化简一下： $max(b_i,a_{i+1})+a_i+b_{i+1}<=max(b_{i+1},a_i)+a_{i+1}+b_i$ 移项， $max(b_i,a_{i+1})-a_{i+1}-b_i<=max(b_{i+1},a_i)-a_i-b_{i+1}$ 其实这个式子的含义是： 两边的较大值会被减掉，较小值的相反数会留下来 所以，其实是： $-min(a_{i+1},b_i)<=-min(a_i,b_{i+1})$ 也就是： $min(a_i,b_{i+1})<=min(a_{i+1},b_i)$ 看似是一个很简单的公式！！ 那么直接排序？ luogu反正是AC了。 但是其实不对！ 我们发现，这个式子不具有传递性， 也就是说， 这种重载小于号的方式，并不满足 $a<=b,b<=c \space\ \to \space\ a<=c$ 手动出几组就可以hack掉。 而我们的sort本质是快速排序实现的。 我们分治的每层子区间会选择一个随机的x作为基准，把小于x放在x左边，大于x放在x右边， 这个排序的正确性，显然要有<满足传递性的性质才行。 所以，这个式子用sort排出来，根据原始输入顺序、基准的x选取的不同，排出来的顺序也是不同的，答案也就是不同的了。 **那么怎么办？** 继续观察这个式子： $min(a_i,b_{i+1})<=min(a_{i+1},b_i)$ 可以（也许很难）想到，和ai，bi本身有关系？ 显然，如果排序的式子和ai，bi本身放在一起，是一定有传递性的。 (例如： $min(a_1,b_1)<=min(a_2,b_2),min(a_2,b_2)<=min(a_3,b_3) \space\ \to \space\ min(a_1,b_1)<=min(a_3,b_3)$ ) 我们只好讨论了。 1.$a_i<b_i,a_{i+1}<b_{i+1}$ 那么就是：$a_i<=a_{i+1}$ 所以这一块按照a升序排序。 2.$a_i=b_i,a{i+1}=b_{i+1}$ 随便排即可。 3.$a_i>b_i,a_{i+1}>b_{i+1}$ 那么就是：$b_{i+1}<=b_i$ 所以这一块按照b降序排序 那么，现在所有的序列会被分成这三大块。 块与块之间怎么办？ 1应该在2前面。2应该在3前面。 即1前，2中，3后。 证明： 1在2前面，2在3前面显然可以证明。 设1、3中的一个元素分别是$(a_1,b_1),(a_3,b_3)$ 因为有$a_1<b_1,a_3>b_3$ 所以，一定有$min(a_1,b_3)<=min(a_3,b_1)$ ### 每个组内部有传递性，组与组之间也有传递性。 所以这种排序就具有传递性。 这样就可以了。 为了方便，可以定义一个人的组别d为： $\frac{a_i-b_i}{|a_i-b_i|}$ 1组对应-1，2组对应0，三组对应1 所以，我们的排序可以这样进行 先按照d为第一关键字，分到每个组里。 d相同，按照组内的排序方式。 完结撒花~~~