P1080 国王游戏贪心证明

本题解是对按左右手乘积排序的贪心证明。

设第

i

、

j

两个人，

i

、

j

相邻，

i

左手

a[i]

、右手

b[i]

，

j

左手

a[j]

、右手

b[j]

。

如果 $i$ 在 $j$ 前面，对最终答案的影响值是 $a[0]\div b[j]$ （ $a[0]$ 为国王左手的数， $b[j]$ 为大臣j右手的数）和 $(a[0]\times a[i])\div b[j+1]$ （ $a[i]$ 为大臣 $i$ 左手的数， $b[j+1]$ 为大臣 $j+1$ 右手的数，以此类推）。
如果 $j$ 在 $i$ 前面，对最终答案的影响值是 $a[0]\div b[i+1]$ 和 $(a[0]\times a[j])\div b[i]$ 。

要保持 $i$ 在 $j$ 前面使得答案更小，必须满足：
- $a[0]\div b[j] < a[0]\div b[i+1]$ 和 $(a[0]\times a[i])\div b[j+1] < (a[0]\times a[j])\div b[i]$ 。
- 由于 $a[0]$ 是固定的，所以可以去掉，得到 $1\div b[j] < 1\div b[i+1]$ 和 $a[i]\div b[j+1] < a[j]\div b[i]$ 。
- 注意到 $1\div b[j]$ 总是小于等于 $a[k]\div b[j]$ （其中 $a[k]$ 为任意大臣左手的数）， $a[i]\div b[j+1]$ 总是大于等于 $1\div b[j+1]$ ，所以只需满足 $a[i]\div b[j+1] < a[j]\div b[i]$ ，即 $a[i]\times b[i] < a[j]\times b[j]$ 。

文章操作