国王游戏 题解
题目
没看题目的自己看
满分算法
(贪心) $O(nlogn)$
本题目实现简单,但是推导难。我们按照每位大臣左右手上的数字升序乘积排序就是答案了。具体的推导过程如下:
假设第i位大臣左手数据是$l_i$,右手数据是$r_i$,国王的数据是$l_0$,$r_0$。
对于任意的第$m$,$m+1$位大臣,他们交换前的奖励是
$\frac{\prod_{i=1}^{m-1}l_i}{r_m}$和$\frac{\prod_{i=1}^{m}l_i}{r_{m+1}}$
交换后的奖励是
$\frac{\prod_{i=1}^{m-1}l_i}{r_{m+1}}$和$\frac{\prod_{i=1}^{m-1}l_i*l_{m+1}}{r_{m}}$
化简得到,我们只需要比较:
$max(\frac{1}{r_m},\frac{l_m}{r_{m+1}})$和$max(\frac{1}{r_{m+1}},\frac{l_{m+1}}{r_{m}})$
同时乘上 $r_ir_{i+1}$ 得
$ max(r_{m+1},l_mr_m) $ 和 $ max(r_{m},l_{m+1}r_{m+1}) $
因为$l_mr_m>r_m$,$r_{m+1}<l_{m+1}r_{m+1}$,
所以当$l_mr_m>l_{m+1}r_{m+1}$时,交换优,
当$l_mr_m<l_{m+1}r_{m+1}$时,不交换优。
所以我们要让乘积小的大臣在前,乘积大的在后,这样最优。
证毕。
代码我就不发了。
作者:方彦哲
Fesdrer
谢谢观看!