学步园

92.
1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,
前面的人比后面的人高(两人身高一样认为是合适的),  那么我们就认为这两个人是一对“捣
乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,
不用具体的对)
要求：
输入:
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
输出：
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。
详细说明自己的解题思路，说明自己实现的一些关键点。

并给出实现的代码，并分析时间复杂度。

限制：
输入每行的最大数字个数为 100000  个，数字最长为 6  位。程序无内存使用限制。

/*
92.
1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,
前面的人比后面的人高(两人身高一样认为是合适的),  那么我们就认为这两个人是一对“捣
乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,
不用具体的对)
要求：
输入:
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
输出：
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。
详细说明自己的解题思路，说明自己实现的一些关键点。
并给出实现的代码，并分析时间复杂度。

求逆序数的个数，用归并实现 就是排序 然后统计一下 违反排序的个数 
*/
#include <iostream>
#include<stdio.h>
using namespace std ;

void merge(int *a,int *p,int start,int mid,int end,int &count)
{
	int i,j,k;
	for(i=start;i<=mid;i++)   // 将数据复制到辅助空间
		p[i]=a[i] ;
	for(j=mid+1;j<=end;j++)
		p[j]=a[j];

	i=start;
	j=mid+1;
	int w=start;
	// 将2个部分进行合并 
	while(i<=mid&&j<=end)
	{
		if(p[i]<=p[j])//左边小于等于右边  复制左边 
			a[w++]=p[i++];
		else		//左边大于右边  复制右边 
		{
			count+=mid-i+1; //左边大于右边 正常应该小于右边 当a[w]=右边 
							//说明原来左边到mid的所以数都大于右边这个数 都是捣乱分子							 
			for(k=i;k<=mid;k++)//输出捣乱分子 
				printf("(%d,%d) ",p[k],p[j]);
			
			a[w++]=p[j++];
		}
	}
	while(i<=mid)
		a[w++]=p[i++];
	
	while(j<=end)
		a[w++]=p[j++];
}

void mergeSort(int *a, int *p, int start, int end, int &count)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		mergeSort( a, p, start, mid, count);
		mergeSort( a, p, mid + 1, end, count);
		merge(a,p,start,mid,end,count);
	}
}

int main()
{
	int a[5]={176,178,180,170,171};
    int n,count,i;
    int *p=new int[5];
	
	count=0;n=5;
	for(i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<"数列中捣乱分子为："<< endl;
	mergeSort(a,p,0,n-1,count);
	cout<<"\n"<<"个数为："<<count<<endl;
    
    delete [] p;
	return 0;
}