【算法日记 11】贪心之美：用“相邻交换法”秒杀乱序求极值问题

【算法日记 11】贪心之美用“相邻交换法”秒杀乱序求极值问题 场景引入百醇的终极摆放艺术今天遇到了一道看似毫无头绪的排列极值题题目大意有NNN根百醇每根有长度AiA_iAi​和美味值BiB_iBi​。我们要把它们首尾相接排成一排。假设第iii根的起点坐标是xix_ixi​我们要最大化总美味值公式∑(xi⋅Bi)\sum (x_i \cdot B_i)∑(xi​⋅Bi​)。数据规模N≤104N \le 10^4N≤104。这道题的物理画面是越往后放的百醇它的坐标xxx就越大。直觉告诉我们如果一根百醇美味值BBB极大我们应该尽量把它往后放去乘上那个巨大的坐标xxx。如果一根百醇长度AAA极大我们应该尽量把它往前放这样能把后面所有百醇的坐标xxx都向后狠狠推一大步但直觉终归是直觉如果一根百醇“又长又美味”我们到底该把它放哪这时我们需要祭出贪心算法的终极武器相邻交换法微扰法✨ 满级数学降维相邻交换法证明假设我们已经排好了一个极其完美的序列。现在我们从队伍里揪出相邻的两根百醇前面的叫甲后面的叫乙。设在甲之前前面百醇累积的坐标是XXX。【情况 1甲在前乙在后】甲的起点是XXX对总分的贡献是X⋅B甲X \cdot B_甲X⋅B甲​乙的起点是XA甲X A_甲XA甲​对总分的贡献是(XA甲)⋅B乙(X A_甲) \cdot B_乙(XA甲​)⋅B乙​两人总贡献X⋅B甲X⋅B乙A甲⋅B乙X \cdot B_甲 X \cdot B_乙 A_甲 \cdot B_乙X⋅B甲​X⋅B乙​A甲​⋅B乙​【情况 2如果两人互换位置乙在前甲在后】乙的起点是XXX对总分的贡献是X⋅B乙X \cdot B_乙X⋅B乙​甲的起点是XA乙X A_乙XA乙​对总分的贡献是(XA乙)⋅B甲(X A_乙) \cdot B_甲(XA乙​)⋅B甲​两人总贡献X⋅B甲X⋅B乙A乙⋅B甲X \cdot B_甲 X \cdot B_乙 A_乙 \cdot B_甲X⋅B甲​X⋅B乙​A乙​⋅B甲​ 见证奇迹的时刻对比上面两个总贡献的式子你会发现前面两项X⋅B甲X⋅B乙X \cdot B_甲 X \cdot B_乙X⋅B甲​X⋅B乙​是一模一样的唯一的区别就在于尾巴上的交叉乘积A甲⋅B乙A_甲 \cdot B_乙A甲​⋅B乙​对比A乙⋅B甲A_乙 \cdot B_甲A乙​⋅B甲​。既然我们要让总分最大那谁排前面更好呢只要A甲⋅B乙A乙⋅B甲A_甲 \cdot B_乙 A_乙 \cdot B_甲A甲​⋅B乙​A乙​⋅B甲​那么甲就绝对应该排在乙的前面如果两边同时除以B甲B_甲B甲​和B乙B_乙B乙​这就等价于A甲B甲A乙B乙\frac{A_甲}{B_甲} \frac{A_乙}{B_乙}B甲​A甲​​B乙​A乙​​。即“长度/美味值”的性价比越高的越该排在前面。我们就这样用初中数学极其优雅地推导出了绝杀的排序比较器 隐藏的“百亿级”数据炸弹逻辑完美了但在敲代码前必须要警惕数据溢出N≤104N \le 10^4N≤104Ai,Bi≤104A_i, B_i \le 10^4Ai​,Bi​≤104。坐标最大可能达到104×10410810^4 \times 10^4 10^8104×104108。单个百醇的得分X⋅BiX \cdot B_iX⋅Bi​可能达到108×104101210^8 \times 10^4 10^{12}108×1041012。总得分累加起来可能达到104×1012101610^4 \times 10^{12} 10^{16}104×10121016。101610^{16}1016远远超过了普通int的极限2×1092 \times 10^92×109所以所有涉及坐标计算和求和的变量必须统统使用long long 光速 AC 模板#includeiostream#includevector#includealgorithmusingnamespacestd;// 将百醇打包成结构体structPocky{longlonga;// 长度longlongb;// 美味值};// 核心比较器相邻交换法推导出的贪心法则boolcmp(constPockyp1,constPockyp2){// 如果 p1 放前面带来的收益 p2 放前面带来的收益p1 就该排前面// 用乘法代替除法完美避免浮点数精度误差returnp1.a*p2.bp2.a*p1.b;}voidsolve(){intn;cinn;vectorPockyp(n);// 分别读入长度和美味值for(inti0;in;i)cinp[i].a;for(inti0;in;i)cinp[i].b;// 按照贪心法则进行光速排序时间复杂度 O(N log N)sort(p.begin(),p.end(),cmp);longlongtotal_delicious0;// 记录总美味值longlongcurrent_x0;// 记录当前累积的坐标起点// 遍历计算得分for(inti0;in;i){total_deliciouscurrent_x*p[i].b;// 加上当前的得分current_xp[i].a;// 起点向后推移}couttotal_delicious\n;}intmain(){// 竞赛必备读写极速引擎ios::sync_with_stdio(false);cin.tie(0);intt;if(cint){while(t--){solve();}}return0;} 首席质检员的总结“相邻交换法”是算法竞赛证明贪心策略的最强武器之一。当你遇到“一维数组排列求极值”、“任务调度求最小延迟”、“打怪兽求最小掉血”等题目时只要你在脑子里想象揪出相邻的两个元素换一换往往就能一秒击碎出题人的障眼法写出完美无瑕的自定义sort比较器