早教吧 育儿知识 作业答案 考试题库 百科 知识分享

设(i1i2i3...in)的逆序数等于k,则(in...i3i2i1)的逆序数为多少?求详解...

题目详情
设(i1i2i3...in)的逆序数等于k,则(in...i3i2i1)的逆序数为多少?求详解...
▼优质解答
答案和解析
方法是将前面的一个个移到in后面
原始 移动后 移动次数
i1 i2 i3. . . in --> i2 i3. . . in i1 n-1次
i2 i3. . . in i1 -->i3. . . in i2 i1 n-2次
.
. 1次
加起来:n(n-1)/2 总逆序数:k+n(n-1)/2