2018.11.07 NOIP模拟 分糖果(贪心)

时间:2023-03-09 22:21:08
2018.11.07 NOIP模拟 分糖果(贪心)

传送门

考虑 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)。

这样得到的新队伍一定是满足题目要求的最优解之一,当然还可能存在其它最优解。

代码