本题看似博弈,但核心是静态选择问题。
由于两人只能删除自己的数字,最终结果只取决于他们最后各自留下的一个数。
分析月默的策略:她希望最终差值尽量大,因此一定会保留自己数字序列中的最小值与最大值,这样无论贪吃佘选哪个数,她都能选出离得最远的那个。
因此问题可转化为:已知 BminB_minBmin 和 BmaxB_maxBmax,贪吃佘需要在自己的序列 AAA 中选择一个数 aia_iai,最小化:max(∣ai−Bmin∣,∣ai−Bmx∣)max(|a_i−B_min|,|a_i−B_mx|)max(∣ai−Bmin∣,∣ai−Bmx∣)。
枚举 aia_iai 计算该值取最小即可。
时间复杂度:o(n)o(n)o(n)。
注册一个 NanXiao OpenAtom Club Online Judge 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 NanXiao OpenAtom Club Online Judge 通用账户