社区讨论

关于 Compare

CF1514E Baby Ehab's Hyper Apartment参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lva8ibpk
此快照首次捕获于
2024/04/22 08:44
2 年前
此快照最后确认于
2024/04/27 00:55
2 年前
查看原帖
众所周知 std::sortstd::stable_sort 的比较函数都要求满足 Compare,其中一条要求是传递性(应该可以这么叫)
comp(a, b) == truecomp(b, c) == truecomp(a, c) == true
但是本题的操作 1 并不满足这一点,因为显然,即使 aabb 之间的边方向是 aba\to bbbcc 之间的边方向是 bcb\to c,也不影响 aacc 之间的边的方向,完全有可能出现 comp(a, b) == truecomp(b, c) == truecomp(a, c) == false 的情况。
实际上因为只需要找一条哈密顿路径,不满足这一点也可以进行这种类似排序的操作,所以我手写了快速排序通过本题。
但是题解区有代码使用了 stable_sort,理论上会导致 RE 等各种情况,实际上我测试了发现 sortstable_sort 都能通过,这是否说明只要满足类似本题中的一些特殊性质,这样使用也不会出问题?

回复

3 条回复,欢迎继续交流。

正在加载回复...