ACM题目,排序。求高手解答。思路或者代码
发布网友
发布时间:2023-11-19 19:04
我来回答
共2个回答
热心网友
时间:2024-01-02 16:23
如果没有相等的情况的话,那么输入可以看成是一个排列
每一种情况有2个分支。
分支1:将最大的数匹配到对应位置,这步可能花费1步或2步
分支2:获得排列的转置,该排列等价于其置换。这一步花费步数0
按最短路来写,需要判重,因为非常多重复状态,当n为24大概就10多万的状态点
如果输入有相等的情况,暂时没有好办法,估计数据中没有相等的情况,如果确实存在相等的情况,由于这是一个考察置换群的题目,那么看看有重复的置换群状态如何求吧
热心网友
时间:2024-01-02 16:23
这个题目是oj上的吗?初步想的是贪心一下可是不知道对不对,就是每次把当前最大的移到后面