国王游戏

重排大臣顺序,最小化最大奖励;按左右手数字乘积升序排序,高精度计算。

来源 Luogu P1080 · 标签 贪心 / 排序 / 高精度 / 交换论证

题目描述

国王和 𝑛 位大臣各有一个左手中的数 𝑎𝑖 和右手中的数 𝑏𝑖。国王固定站在队伍最前面,大臣可以重新排列。

若大臣 𝑗 前面所有人的左手中的数乘积为 𝑆,则他的奖励为 𝑆𝑏𝑗。求一种排列,使所有大臣奖励的最大值最小,输出这个最小值。

1≤𝑛≤1000,1≤𝑎𝑖,𝑏𝑖≤104。

题解

把国王编号为 0,大臣编号为 1,…,𝑛。本题是静态全序的实例:

  • 𝐸={1,…,𝑛}:所有大臣;
  • 状态 𝑠:已经排好的前缀;
  • 𝐴(𝑠):尚未排列的大臣;
  • 𝜅(𝑖)=𝑎𝑖𝑏𝑖;
  • 𝑔(𝑠)∈argmin𝑖∈𝐴(𝑠)𝑎𝑖𝑏𝑖;
  • 动作序列 𝜋=(𝑝1,…,𝑝𝑛):大臣的排列,其中 𝑝0=0 是国王;
  • 目标值

    𝐶(𝜋)=max1≤𝑗≤𝑛∏𝑘=0𝑗−1𝑎𝑝𝑘𝑏𝑝𝑗.

因此按 𝑎𝑖𝑏𝑖 从小到大排序,然后依次计算前缀乘积并取奖励最大值。

相邻交换可以说明这个顺序最优。设两个相邻大臣为 𝑖,𝑗,他们前面的左手中的数乘积为 𝑆。比较两种顺序:

max(𝑆𝑏𝑖,𝑆𝑎𝑖𝑏𝑗)与max(𝑆𝑏𝑗,𝑆𝑎𝑗𝑏𝑖).

约去公共因子后,𝑖 排在 𝑗 前不劣当且仅当 𝑎𝑖𝑏𝑖≤𝑎𝑗𝑏𝑗。因此按 𝑎𝑖𝑏𝑖 升序排列不会比任何相邻交换更差,交换论证归纳即得最优。

乘积和奖励会超过 64 位整数范围,需要用高精度整数保存前缀乘积和答案。

复杂度

排序为 𝑂(𝑛log𝑛);高精度乘除的开销取决于数字位数。空间主要取决于高精度数,为 𝑂(𝑛) 个十进制位级别。

参考

源码位置