[NOIP2012]国王游戏


题解

内容摘自李煜东所著《算法竞赛进阶指南》
由于本题输出过大,要用高进度,但是这里主要讨论贪心,请先无视高精度

按照每个大臣左、右手上的数的乘积从小到大排序,就是最优排队方案。这个贪心算法可以使用微扰(临项交换)证明。
对于任意一种排序,设\(n\)名大臣左、右手上的数分别是\(A[1]\)到\(A[n]\)与\(B[1]\)到\(B[n]\),国王里的数是\(A[0]\)和\(B[0]\)。
如果我们交换两个相邻的大臣\(i\)与\(i+1\),在交换前这两个大臣获得的奖励是:


\(\displaystyle \frac{1}{B[i]} \times \prod_{j=0}^{i-1} A[j] \)与\(\displaystyle \frac{1}{B[i+1]} \times \prod_{j=0}^i A[j]\)

交换之后这两个大臣获得的奖励是:


\(\displaystyle \frac{1}{B[i+1]} \times \prod_{j=0}^{i-1} A[j] \)与\(\displaystyle \frac{A[i+1]}{B[i]} \times \prod_{j=0}^{i-1} A[j]\)

其他大臣获得的奖励显然都不变,因此我们只需要比较上面两组式子最大值的变化。提取出公因式\(\prod_{j=0}^{i-1}A[j]\)后,实际上需要比较下面两个式子的大小关系:


\(max(\frac{1}{B[i]},\frac{A[i]}{B[i+1]})\) ——\(max(\frac{1}{B[i+1]},\frac{A[i+1]}{B[i]})\)

两边同时乘上\(B[i]\times B[i+1]\),变为比较:


\(max(B[i+1],A[i]\times B[i])\) ——\(max(B[i],A[i+1]\times B[i+1])\)

注意到大臣手上的树都是正整数,故\(B[i+1]\le A[i+1]\times B[i+1]\),且\(B[i] \le A[i]\times B[i]\)。

于是,当\(A[i]\times B[i]\le A[i+1]\times B[i+1]\)时,\(左式\le 右式\),交换前更优。当\(A[i+1]\times B[i+1]\le A[i]\times B[i]\)时\( 右式\le 左式\),交换后更优。也就是说,在任何局面下,减小逆序对数都不会造成整体结果变差,而增加逆序对数则不会使整体结果变好。

最后,根据冒泡排序的知识,任何一个序列都能通过邻项交换的方式变为有序序列。故当逆序对数为0,即按上述方案排序时就是最优策略。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注