P1080 [NOIP 2012 提高组] 国王游戏 题解复盘

P1080 [NOIP 2012 提高组] 国王游戏 题解复盘模块贪心算法目标重新排列大臣顺序使获得奖金最多的大臣奖金尽可能少基本信息项目内容题目编号、来源P1080 洛谷 / [NOIP 2012 提高组] 国王游戏训练层级B 提高贪心知识版块贪心、交换排序、高精度计算解题前・关键信号识别维度分析目标、约束、底层结构目标调整大臣排列顺序使所有大臣中奖金中的最大值最小。约束每个大臣有左右手两个数字奖金受到前面所有大臣左手乘积影响。底层结构排列顺序会影响结果因此考虑交换相邻两个大臣通过比较交换前后的结果推出排序规则。数据规模n≤1000a、b较大前缀乘积会远超 long long需要使用高精度存储。候选算法和依据算法交换贪心 高精度。依据通过交换两个相邻大臣分析可得应该按照a*b从小到大排序使大的影响尽可能靠后。复杂度预判排序 O(nlogn)。每个大臣进行一次高精度乘法和除法长度为乘积位数。空间复杂度 O(n)。解题后・外化复盘维度内容实现结构 / 核心思路1. 将每个大臣的左右手数字存入结构体。2. 按照a*b从小到大排序。3. 使用高精度数字维护当前所有前面人的左手乘积。4. 遍历排序后的大臣① 当前奖金 当前乘积 ÷ 当前大臣右手数字。② 更新最大奖金。③ 当前乘积 × 当前大臣左手数字。错因回溯1. 容易按照 a 或 b 单独排序但真正影响交换的是 a*b。2. 容易把当前大臣自己的左手数字提前乘入导致奖金计算错误。3. 容易忽略乘积过大需要使用高精度。边界和易错点1. 高精度数字需要使用 vector 保存。2. 大整数通常低位在前存储方便乘法。3. 计算奖金时必须先除后乘。4. 答案需要高精度比较不能使用普通变量。下次看到什么信号我应该想到这个方法看到① 多个对象需要排序② 排列顺序影响最大值③ 可以通过交换相邻元素比较优劣想到交换贪心推导排序规则。AC 完整代码#includeiostream#includealgorithm#includevector#includestack#includequeue#includemapusingnamespacestd;structnode{longlonga,b;};boolcmp(node x,node y){returnx.a*x.by.a*y.b;}vectorintmul(vectorinta,intb){vectorintc;intt0;for(inti0;i(int)a.size();i){intxa[i]*bt;c.push_back(x%10);tx/10;}while(t){c.push_back(t%10);t/10;}returnc;}vectorintdiv(vectorinta,intb){vectorintc;intr0;for(intia.size()-1;i0;i--){rr*10a[i];c.push_back(r/b);r%b;}reverse(c.begin(),c.end());while(c.size()1c.back()0)c.pop_back();returnc;}boolbigger(vectorinta,vectorintb){if(a.size()!b.size())returna.size()b.size();for(intia.size()-1;i0;i--){if(a[i]!b[i])returna[i]b[i];}returnfalse;}voidprint(vectorinta){for(intia.size()-1;i0;i--)couta[i];coutendl;}intmain(){intn;cinn;vectornodev(n);longlongkingA,kingB;cinkingAkingB;for(inti0;in;i){cinv[i].av[i].b;}sort(v.begin(),v.end(),cmp);vectorintsum;sum.push_back(kingA);vectorintans;ans.push_back(0);for(inti0;in;i){vectorintcurdiv(sum,v[i].b);if(bigger(cur,ans)){anscur;}summul(sum,v[i].a);}print(ans);return0;}