Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:算法!查了老长时间的资料才查出来的!不容易呀!

Posted by ych_tiger at 2008-01-20 16:47:22 on Problem 1674
In Reply To:算法!查了老长时间的资料才查出来的!不容易呀! Posted by:OIer_nk2008 at 2007-07-08 11:33:34
> {3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列
> {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }比较
> 找出其中所有的"环"
> 这里的"环"就是指它们互相交换之后能成为标准序列的最小集合
> 比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
> 具体找法很简单 首先确定一个不在已找出"环"中的数字 
> 例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开始的数字 那么这个环就是{1,3}
> 第二次从7开始,7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8}
> 第三个环是{6,4}
> 这样所有的数字都在环中了
> 交换的次数=(数字总数-环数)=8-3=5
简单模拟不就可以了  弄这个算法到麻烦了 复杂度O(n);

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator