做网站需要的法律知识,南昌定制网站开发,做网站需要填什么,wordpress获取文章标签题目#xff1a;
给一列数a1,a2,…,an#xff0c;求它的逆序对数#xff0c;即有多少个有序对(i,j)#xff0c;使得i j但aiaj。n可以高达1e6
分析与解答
由于是从小到大进行合并操作#xff0c;可以发现如果右半数组的元素q放入临时空间中#xff0c;那么左半…题目
给一列数a1,a2,…,an求它的逆序对数即有多少个有序对(i,j)使得i j但aiaj。n可以高达1e6
分析与解答
由于是从小到大进行合并操作可以发现如果右半数组的元素q放入临时空间中那么左半数组中当前元素p到末尾的元素m全部都是大于q的左边所剩元素在区间[p,m)中因此元素个数为m-p此时满足右边下标大于左边但是右边的数小于左边这一条件 所以只需在分治排序的基础上增加一个累加对于q来说它的逆序数有m-p个那就累加上即可
#includeiostream
using namespace std;
int cnt0;
void merge_sort(int *a,int x,int y,int *t){if(y-x1){int mx(y-x)/2;int px,qm,ix;merge_sort(a,x,m,t);merge_sort(a,m,y,t);while(pm||qy){if(qy||(pma[p]a[q]))t[i]a[p];else {t[i]a[q];cntm-p;}}for(int ix;iy;i) a[i]t[i];}
} int main(){int a[100],b[100];for(int i0;i10;i){cina[i];}merge_sort(a,0,10,b);coutcnt;
}
