传送门
考虑 n = 2 时的情况:假定两个人分别为(a, b),(c, d),则当且仅当min(a,d) ≤ min(b,c)时,把(a, b)放在前面更优,否则把(c, d)放在前面更优
然后把n = 2 的结论进行扩展。我们定义第 i 个小朋友比第 j 个小朋友小,当且仅当 min(ai,bj) <min(aj,bi),以这个规则进行排序,时间复杂度 O(nlogn)。
这样得到的新队伍一定是满足题目要求的最优解之一,当然还可能存在其它最优解。
代码
相关文章
- 2018.08.19 NOIP模拟 dp(二分+状压dp)
- HDU 1528 贪心模拟/二分图
- NOIP模拟:能源(二分答案)
- [NOIP2012]疫情控制 贪心 二分
- jzoj100029. 【NOIP2017提高A组模拟7.8】陪审团(贪心,排序)
- [NOIP10.6模拟赛]1.merchant题解--思维+二分
- 7.28 NOI模拟赛 H2O 笛卡尔树 并查集 贪心 长链剖分
- 2018.08.29 NOIP模拟 movie(状压dp/随机化贪心)
- JZOJ5400. 【NOIP2017提高A组模拟10.7】Repulsed 树型DP+贪心
- zoj4062 Plants vs. Zombies 二分+模拟(贪心的思维)