小和问题 逆序对问题c++_小和问题的变体 c++

问题描述：如果一个数组中，右边的数比左边数字大，则构成小和
例：1 3 5 6 7中 1<3 1
1<5 3<5 1 3
1<6 3<6 5<6 1 3 5
1<7 3<7 5<7 6<7 1 3 5 6小和为:1+1+3+1+3+5+1+3+5+6
利用归并排序
（转他人）分析
在归并过程中计算小和，实质是如果左数小于右数，则记录
1 3 4|2 5
/
1 3 |4 2|5
/
1|3
1.在1|3归并中，1<3，产生小和1；
2.在1 3|4归并中，p1指向1，p2指向4。1<4，记录小和1，p1指向3,3<4,继续记录小和3；
3.右侧2|5,2<5，记录小和2；
4.1 3 4 | 2 5中，p1指向1，p2指向2。1<2，则2右侧大于2的数都构成小和，记录小和2个1；
p1移到3处，3>2不记录，p2右移到5,3<5，由于5右侧没有数了，所以记录小和1个3；p1继续右移，4<5，再继续记录小和1个4；
5.小和 = 1+1+3+2+21+13+1*4 = 16

int  merge(int a[], int l, int m, int r)
{
   
	int help[100];
	int i = 0;
	int p1 = l;
	int p2 = m + 1;
	int res = 0;
	while (p1<=m&&p2<=r)
	{
   
		res +
1
2
3
4
5
6
7
8
9
10
11