P1080 国王游戏贪心证明

· · 题解

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

设第 i、j 两个人，i、j 相邻，i 左手 a[i]、右手 b[i]，j 左手 a[j]、右手 b[j]。

  1. 如果 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 右手的数，以此类推）。

  2. 如果 j 在 i 前面，对最终答案的影响值是 a[0]\div b[i+1] 和 (a[0]\times a[j])\div b[i]。

    要保持 i 在 j 前面使得答案更小，必须满足：

    • 由于 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]。