..
AcWing 114. 国王游戏
按照每个大臣左、右手上的数的乘积从小到大排序，就是最优排队方案。
这个贪心可以使用微扰（邻项交换）证明。
对于任意一种顺序，设 $n$ 名大臣左、右手上的数分别是 $A[1] \sim A[n]$ 与 $B[1] \sim B[n]$，国王手里的数是 $A[0]$ 和 $B[0]$。
如果我们交换两个相邻的大臣 $i$ 与 $i + 1$，在交换前这两个大臣获得的奖励是：
\[{ {1} \over {B[i]} } * \prod_{j = 0}^{i - 1}{A[j]} \; 与 \; { {1} \over {B[i + 1]} } * \prod_{j = 0}^{i}{A[j]}\]交换之后这两个大臣获得的奖励是：
\[{ {1} \over {B[i + 1]} } * \prod_{j = 0}^{i - 1}{A[j]} \; 与 \; { {A[i + 1]} \over {B[i]} } * \prod_{j = 0}^{i - 1}{A[j]}\]其他大臣获得的奖励显然都不变，因此我们只需要比较上面两组式子最大值都变化。
提取公因式 $\prod_{j = 0}^{i - 1}{A[j]}$ 后，实际上需要比较下面两个式子的大小关系：
\[\max({ {1} \over {B[i]} }, { {A[i]} \over {B[i + 1]} }) \quad max({ {1} \over {B[i + 1]} }, { {A[i + 1]} \over {B[i]} })\]两边同时乘上 $B[i] * B[i + 1]$，变为比较：
\[\max(B[i + 1], A[i] * B[i]) \quad \max(B[i], A[i + 1] * B[i + 1])\]注意到大臣手上的数都是正整数，故 $B[i + 1] \leq A[i + 1] * B[i + 1]$，且 $A[i] * B[i] \leq B[i]$。
于是，当 $A[i] * B[i] \leq A[i + 1] * B[i + 1]$ 时，左式 $\leq$ 右式，交换前更优。
当 $A[i] * B[i] \geq A[i + 1] * B[i + 1]$ 时，左式 $\geq$ 右式交换后更优。
也就是说，在任何局面下，减小逆序对数都不会造成整体结果变差，而增加逆序对数则不会使整体结果变好。
最后，根据冒泡排序的知识，任何一个序列都能够通过邻项交换的方式变为有序序列。
故当逆序对数为 $0$，即上述方案排序时就是最优策略。