首页 > 代码库 > 逆序对
逆序对
逆序对就是说在一个集合里边满足i<j && a[i]>a[j]的一对元素（或者a[i]<a[j]，也可以是|，∈等其他奇奇怪怪的偏序）（一般还是>和<用的多）
当定义逆序对的偏序是>的时候逆序对个数的意义就是给这些数升序冒泡最少交换的次数
为什么呐
如果i<j && a[i]<a[j]，呢么这两个数可以“平行”地移过去而不进行交换，反之如果a[i]>a[j]，呢么a[i]要往右走，a[j]要往左走，但是a[i]又在a[j]的左边，这两个数一定会相遇，就不可避免地要交换
怎么求呐
可以使用归并排序，在合并的时候就将逆序对的个数计算出来
核心思想就是在合并的时候，如果a[i]>a[j]，呢么一直到归并的中间点都是逆序对，归并的两半都已经单调递增了，a[i]比a[j]大，a[i+1~mid]也一定比a[j]大
代码:
1 int c[110000]; 2 int d[110000],dtou=0; 3 int bowl=0; 4 void bing(int _left,int _right){ 5 int mid=(_left+_right)/2; dtou=_left-1; 6 int i=_left,j=mid+1; 7 while(i<=mid && j<=_right){ 8 if(c[j]<c[i]){ d[++dtou]=c[j++]; bowl=(bowl+mid-i+1)%mo;} 9 else d[++dtou]=c[i++];10 }11 while(i<=mid) d[++dtou]=c[i++];//序列是单调的，所以后面的肯定也都大于前面的12 while(j<=_right) d[++dtou]=c[j++];13 for(int i=_left;i<=_right;i++)14 c[i]=d[i];15 }16 void gui(int _left,int _right){17 if(_left<_right){18 int mid=(_left+_right)/2;19 gui(_left,mid),gui(mid+1,_right);20 bing(_left,_right);21 }22 }
逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。