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

提供2组数据 + 提示

Posted by halfapri at 2016-08-23 21:28:42 on Problem 3581 and last updated at 2016-08-24 01:09:07
input
9
9 -2 8 1 1 8 1 1 1

output:
-2 9 1 1 8 1 1 1 8


input
9
9 -2 8 1 1 8 1 1 2

output
-2 9 1 1 8 1 1 8 2

tip:
(1) 因为A[1]>A[2~n],所以我们对A[] reverse后,求出sa[]后:
选择sa[i]>1 && (i为最小)对应的sa[i]作为第一个part必定是最优的
(2) 经过(1)操作后,剩下的问题变成了给出一个a[1~n],求分成两部分并分别revese后再重组后的a'[]的字典序最小。。。。
这部分稍微动下脑筋就出来了,就不废话了= =
https://github.com/halfapri/half/blob/master/borc/string/poj3581/A.cpp

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