- 主题:求一个题目的非暴力算法
每次把未处于应处位置的最小的数翻转到他应该处的位置,比如3 1 2->1 3 2-> 1 2 3。2 3 4 5 6 1->1 6 5 4 3 2 -> 1 2 3 4 5 6
没想到怎么证明这是最少步数,但也没发现反例
========================================
=====想了想,完全不对,反例一大堆。=====
========================================
【 在 SHENOK 的大作中提到: 】
: 题目: 给定前N个自然数的一个乱序排列, 比如 3 1 2, 求能让其顺序排列的最小操作次数。其“操作”只有一种,即对任何一个子序列反序。 所以,312,需要操作两次 312-》321-》123。输出2.
: 输入4321 ,输出1.
:
: ...................
--
修改:zhutou3 FROM 1.119.170.*
FROM 1.119.170.*
好例子,但您看这个case和上面我提的算法其实是一样的,只是从最大的开始sort
【 在 Jangbi 的大作中提到: 】
: 436512->432156->123456
: 436512->156342->124365->123465->123456
:
--
FROM 1.119.170.*
从另一端:4326517,4321567,1234567 :)
【 在 maruko 的大作中提到: 】
: 7156234,
: 你的方法1756234,1265734,1237564,1234657,1234567,5步。
: 最短7651234,7654321,1234567,3步
: ...................
--
FROM 1.119.170.*
那个方法得到的应该只是一个可行解,不是最优解
【 在 maruko 的大作中提到: 】
: 7156234,
: 你的方法1756234,1265734,1237564,1234657,1234567,5步。
: 最短7651234,7654321,1234567,3步
: ...................
--
FROM 1.119.170.*