Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
公式的一种解释每个排列a1a2...an唯一对应一个反序列表b1b2...bn,例如 5 9 1 8 2 6 4 7 3 有反序表 2 3 6 4 0 2 2 1 0 bj为位于j左边但大于j的元素个数 冒泡排序交换相邻元素,改变对应的反序数。如果对应的反序数大于0,则减1. 因此对一个排列使用冒泡排序的扫描次数k = max{bj} 任给一个k,求对应的排列数就是求反序数最大值为k的反序表的个数, 反序表每位上的反序数的取值范围为[0, n - i]. 这样就能得到对应的反序表个数为 k! * ((k + 1)^(n - k) - k ^(n - k)) 详细介绍见程序设计艺术第三卷第1节 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator