题目 题意: 给定一个自造的排序规则，依次输出参数为0-n时的元素交换次数。 思路: 第一次循环，把a[1]和>a[1]的元素都循环右移动，最大的元素会放到a[1]的位置。 第2-n次循环，前(i-1)个元素已然升序排序。 考虑元素各不相同。 对于第i个元素(i>=2)，假设前i-1个数中碰到的第一个比他大的数下标为k，那么所有k-i-1的数都会跟她交换一次，贡献为k-i，即前i个数中比a[i]大的数的个数。可以用树状数组动态维护。 特别地，对于比a[1]大的数，有额外的1点贡献，并且要和a[1]换位。换位不影响后边的元素求贡献。第一次右移也不影响，因为移走了一个比它大的，但是最大的移动到了最前边。
考虑存在相同的元素，2前边有4、4、5，只会和第一个4换，所以只要去重就好。 但是要考虑到某种特殊情况，设a[1] = x. x … x … y y > x. 当维护到y的时候，第一个x是要和y交换的，交换之后第二个x没有统计到y的贡献。究其原因，我们是动态维护前i个数的贡献，当i指到y的时候，第二个x到y之间
关注
打赏
查看更多评论
