- 主题:求一个题目的非暴力算法
你是要找两个点（312 和123）的最短距离。可以用网络图的最短距离查找的算法。
【 在 SHENOK 的大作中提到: 】
: 题目： 给定前N个自然数的一个乱序排列， 比如 3 1 2， 求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。 所以，312，需要操作两次 312-》321-》123。输出2.
: 输入4321 ，输出1.
:
: ...................
--
FROM 68.97.41.*
是的，但是你不需要显式地事先把图建起来，可以边算距离边加点。
最坏情况可能会相当于把这些节点都建了，但是平均情况应该只要建一小部分。
【 在 SHENOK 的大作中提到: 】
: 是要首先建立一个图吗？
:
: 3个数的序列就是1000个节点，10个数就是10亿个节点？
: ...................
--
FROM 68.97.41.*
要是等价的话，那现在的算法就应该是最经济的了。你可能可以把序列改成哈希值什么玩意的来提升效率，但是不会有复杂度的改进了。
【 在 SHENOK 的大作中提到: 】
: 感觉跟我上面的算法等价啊
: 我那个就是每次走一步， 走到了就退出， 没走到就要记录现场，然后继续。。。。。
:
--
FROM 68.97.41.*