跳到主要内容

贪心:邻项交换排序

邻项交换排序是指:为了最小化 / 最大化某个指标,我们需要设计一个排列,而我们通过设计一种排序方法来求出这个特定的排列。

其中一种有效的方法就是邻项交换排序,即我们讨论序列中相邻的两个项 i,ji,j,考虑交换它们的影响,以及如何排列 i,ji,j 可以实现指标最大化 / 最小化。

这是一种蛮重要的贪心思想。但是要弄明白并不容易。本文的参考资料:

严格弱序

std::sort() 要求我们设计一个满足严格弱序的比较算法。(不过实际上很多 OI 题不这样也能拿很高分甚至 AC,属于是数据水了)。

具体这个是什么请看 序理论

题目