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:不用STL的非递归方法

Posted by YA_ME_DE at 2009-05-21 20:42:26 on Problem 1731
In Reply To:不用STL的非递归方法 Posted by:YA_ME_DE at 2009-05-21 20:21:37
貌似明白了。
比如S[]=1 2 3 4 9 7 6 5
先从右往左,找第一个比右边的数小的数.显然找到i=3(下标从0开始)
注意,这里找到这个数后,隐含的含义就是从i+1到结尾,按降序排列。
找到这个数后,再从右往左找,第一个比S[i]大的数,找到5.
之所以要这么找,无非是要把这个数变大(字典序的定义),而之所以找第一个,是因为S(这里指12349765这个序列)的下一个字典序是S集合能形成的所有序列中大于S的第一个,因此我们只想它增大一小点。而刚好,从右开始找的话,因为从右往左是升序(如前所说,隐含i+1到结尾为降序),因此找到的第一个比S[i]大的数,就是符合要求的数。
到这里,交换数字4和5.
交换以后,i+1到结尾仍然是降序,因为我们交换了一个比刚才未交换时还小的数过去。
所以,这个时候把i+1到结尾反转,即reverse(i+1,end)
那么,反转过后,i+1到end这个串,就是i+1到end这些元素能组合成的最小的值,满足我们找字典序的要求。

欢迎讨论^_^
www.oeddyo.com
菜鸟一个,希望各位多指点,有错误的话帮忙指出一下:)

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