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 ocgcn at 2010-12-23 00:12:24 on Problem 1455
In Reply To:解题思路,及公式的推导,供大家参考 Posted by:xiao1590 at 2007-02-20 12:58:16
> 若是线形无环,将1-n变为n-1,求逆序数n*(n-1)/2即可(线性代数)
> 但本题由于是环,则在1-n中取一k,将1-n变为形如k-1,n-(k+1)也可满足条件,比如1,2,3,4,5变为3,2,1,5,4也可满足条件。问题转换为只需确定一k,使逆序数最小。
> 设一k,对于k-1和n-(k-1)分别求逆序数:
> k-1:k*(k-1)/2
> n-(k+1):(n-k)*(n-k-1)/2
> 则总共的逆序数为k*(k-1)/2+(n-k)*(n-k-1)/2,根据一元二次方程最低点(-b/2a)求得当k=n/2时该式最小
> 将k=n/2代入k*(k-1)/2+(n-k)*(n-k-1)/2有最小值(n/2)*(n/2-1)(或直接根据最值公式(4ac-b^2)/4a)
> 由于n奇偶不确定将公式变为(n/2)*(n-1)/2可用于奇数的情况,发现对于偶数(n-1)/2=n/2-1,故(n/2)*(n-1)/2适用所有情况,得解
> 
> 
> 写得蛮辛苦,觉得对您有用就UP下吧~本人学识浅薄,如有错误请大家及时指出,以免误导他人

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