洛谷P1080 [NOIP2012 提高组] 国王游戏
全序贪心
若国王左手为(a_0)，右手(b_0)
大臣(1)左手(a_1)，右手(b_1)
大臣(2)左手(a_2)，右手(b_2)
则答案
[ans_1=max(frac{a_0}{b_1},frac{a_0*a_1}{b_2})
]
如果交换大臣(1)和大臣(2)，那么答案
[ans_2=max(frac{a_0}{b_2},frac{a_0*a_2}{b_1})
]
而最终的答案
[ans=max(ans_1,ans_2)
]
显然有
[frac{a_0*a_2}{b_1}>frac{a_0}{b_1}，frac{a_0*a_1}{b_2}>frac{a_0}{b_2}
]
所以
[ans=max(frac{a_0*a_2}{b_1},frac{a_0*a_1}{b_2})
]
如果交换两个大臣的位置决策更优，那么
[frac{a_0*a_2}{b_1}<frac{a_0*a_1}{b_2}
]
[a_1*b_1>a_2*b_2
]
以(a*b)为关键字将大臣从小到大排序即可