题解

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

按照每个大臣左、右手上的数的乘积从小到大排序，就是最优排队方案。这个贪心算法可以使用微扰（临项交换）证明。
对于任意一种排序，设\(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，即按上述方案排序时就是最优策略。

代码