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

简单分析

Posted by aoxboxcox at 2013-02-28 17:00:37 on Problem 1346 and last updated at 2013-03-01 10:05:07
(1)“每次只能取红座的人”这一要求其实只限制第一次取人。因为往后要取的人都可以通过前一次移动把他放在红座上。
(2)同理,只要有人被取下并调整位置过,那么此后红蓝座位问题就不用再考虑了。
(3)每个人最多只需要被取下并调整位置1次,且取下的先后顺序可以没有关系。

所以,原题就变成了求把环状数组排序,最少需要调整的元素数。
再接着就变成了求环状数组上最长排序子串的长度。当然,顺便得考虑一下这个子串是否包含了所有的红座。

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