高大大山

文章
4
资源
0
加入时间
4年0月9天

hdu 1394(树状数组求逆序数)

解题思路:这道题是求循环数组中逆序数最小值,求逆序数这里肯定是用树状数组。只是这里有一点点变化,由于题目中n位数是0-n-1的一个排列,所以num[i]可表示为比num[i]小的数的个数。把第一位的数挪到最后一位,那么整个序列的逆序数变化为ans =ans -  num[0] + (n-1-num[0]),num[0]表示后面的n-1位对逆序数的贡献,n-1-num[0]表示把最后一位挪过来对逆序