关于字典序

又遇到字典序的题目了,于是仔细思考了下

通用方法

为了保证字典序最小,最通用的办法就是“我为人人”,倒过来考虑,顺着输出(也可以是顺着考虑,倒过来输出,反正两个方向不能相同)

https://www.cnblogs.com/sahdsg/p/10409765.html

因为倒过来考虑时,能保证最后一个选择的字典序最小,就可以保证在输出的时候第一个选择就是最小的字典序。

排列

HDU 1074

排列的字典序最小也可以“人人为我”,倒过来考虑,顺着输出,每次选择字典序最大的

考虑两个不相等的排列$x_1,x_2,x_3,x_4,x_5$, $y_1,y_2,y_3,y_4,y_5$,当$x_5 geqslant y_5$时,说明比$x_5$小的$y_5$在$x_5$的前面出现,以此类推,到某一个位置以后$x$就一定小于等于$y$,否则与排列矛盾,因此排列$X$就小于排列$Y$

原文地址:https://www.cnblogs.com/sahdsg/p/10903075.html