关于 Compare
查看原帖
关于 Compare
678087
fangzichang楼主2024/4/22 08:43

众所周知 std::sort 和 std::stable_sort 的比较函数都要求满足 Compare,其中一条要求是传递性(应该可以这么叫)

若 comp(a, b) == true 且 comp(b, c) == true 则 comp(a, c) == true

但是本题的操作 1 并不满足这一点,因为显然,即使 aa 和 bb 之间的边方向是 a→ba\to b 且 bb 和 cc 之间的边方向是 b→cb\to c,也不影响 aa 和 cc 之间的边的方向,完全有可能出现 comp(a, b) == true 且 comp(b, c) == true 且 comp(a, c) == false 的情况。
实际上因为只需要找一条哈密顿路径,不满足这一点也可以进行这种类似排序的操作,所以我手写了快速排序通过本题。
但是题解区有代码使用了 stable_sort,理论上会导致 RE 等各种情况,实际上我测试了发现 sort 和 stable_sort 都能通过,这是否说明只要满足类似本题中的一些特殊性质,这样使用也不会出问题?

2024/4/22 08:43
加载中...