该类型的题目少见,但是也涌现出了一些套路。
相关:
题目:国王游戏,皇后游戏(分糖果),数对
参考:c++严格弱序,ouuan,gigo,fsy,zxy
概述
这是一种常见的思路,希望。我们对这个条件进行变形,甚者凭空加强出满足条件的式子。这通常只是题目的切入点。(gigo)
应用
我们使用这个式子作为排序函数来解决偏序要求或者贪心要求。而在《数对》中构建了dp顺序,就像拓扑序一样。
算法正确性
严格弱序
要求
若使用STL库的 sort()
函数需要满足严格弱序(strict weak ordering),否则将出现未定义的行为。设为实现给STL比较的二元布尔关系:,则有
- 传递性(transitivity)
- 反对称性(antisymmetric)
- 不可比的传递性
注意,根据反对称性可以轻松推出反自反性(irrefexibility)。
实现
对于一个要求不强的式子,可以构造出一个强于要求但方便排序的函数。
否则思考调整函数满足关系,比如常见的关键字(第二关键字);或者根据对象的成员属性关系将对象分组,再考虑组内、组与组的排序方法。
跨项还是邻项?
一般直接考虑全局(gigo),如《数对》的简单性质要求,题目直接给出条件。
也可以分析邻项交换前后的贡献,如皇后游戏性质更强的题目,之后推广(fsy):设中间有k项,把前后贡献式子列出来进行对比(zxy)。
题目拥有好的性质
对国王游戏,询问的是和最小:乘积从小到大排序一定最优,且只有这种排法。
对皇后游戏,询问的是最大值最小:根据题目条件有前面大一定不优,因此邻项可推广。不会出现退火的情况。也可以数学尝试推广(zxy)。