枫林晚 的博客

枫林晚 的博客

皇后游戏

posted on 2018-09-24 11:10:58 | under 未分类 |

参考/推荐:题解 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升序排序。

  1. $a_i=b_i,a{i+1}=b_{i+1}$

随便排即可。

  1. $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相同,按照组内的排序方式。

完结撒花~~~