国王游戏
重排大臣顺序,最小化最大奖励;按左右手数字乘积升序排序,高精度计算。来源 Luogu P1080 · 标签 贪心 / 排序 / 高精度 / 交换论证
题目描述
国王和 位大臣各有一个左手中的数 和右手中的数 。国王固定站在队伍最前面,大臣可以重新排列。
若大臣 前面所有人的左手中的数乘积为 ,则他的奖励为 。求一种排列,使所有大臣奖励的最大值最小,输出这个最小值。
,。
题解
把国王编号为 ,大臣编号为 。本题是静态全序的实例:
- :所有大臣;
- 状态 :已经排好的前缀;
- :尚未排列的大臣;
- ;
- ;
- 动作序列 :大臣的排列,其中 是国王;
目标值
因此按 从小到大排序,然后依次计算前缀乘积并取奖励最大值。
相邻交换可以说明这个顺序最优。设两个相邻大臣为 ,他们前面的左手中的数乘积为 。比较两种顺序:
约去公共因子后, 排在 前不劣当且仅当 。因此按 升序排列不会比任何相邻交换更差,交换论证归纳即得最优。
乘积和奖励会超过 位整数范围,需要用高精度整数保存前缀乘积和答案。
复杂度
排序为 ;高精度乘除的开销取决于数字位数。空间主要取决于高精度数,为 个十进制位级别。