社区讨论
关于 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::sort 和 std::stable_sort 的比较函数都要求满足 Compare,其中一条要求是传递性(应该可以这么叫)若comp(a, b) == true且comp(b, c) == true则comp(a, c) == true
但是本题的操作 1 并不满足这一点,因为显然,即使 和 之间的边方向是 且 和 之间的边方向是 ,也不影响 和 之间的边的方向,完全有可能出现
实际上因为只需要找一条哈密顿路径,不满足这一点也可以进行这种类似排序的操作,所以我手写了快速排序通过本题。
但是题解区有代码使用了
comp(a, b) == true 且 comp(b, c) == true 且 comp(a, c) == false 的情况。实际上因为只需要找一条哈密顿路径,不满足这一点也可以进行这种类似排序的操作,所以我手写了快速排序通过本题。
但是题解区有代码使用了
stable_sort,理论上会导致 RE 等各种情况,实际上我测试了发现 sort 和 stable_sort 都能通过,这是否说明只要满足类似本题中的一些特殊性质,这样使用也不会出问题?回复
共 3 条回复,欢迎继续交流。
正在加载回复...