小编alt*_*000的帖子

我得到了集合{1,2,...,n}的排列.我必须通过以最小的总成本交换位于成功位置的数字来排序这种排列.交换位于连续位置的元素x,y的成本是min(x,y).

例如,如果我有排列3,1,2,4总的最小成本是3.因为我执行这些步骤((x,y)意味着用y交换x):

• (3,1),2,4结果1,3,2,4,成本最小(1,3)= 1
• 1,(3,2),4结果1,2,3,4与成本min(2,3)= 2

总费用为3.

我通过交换最小成本未排序对来尝试蛮力,直到没有未排序的对,但这种方法显然不够快.

我的问题是,如何根据我的条件找到最低的分拣成本？