小和問題和逆序對（用對數器驗證）

起因是左神的mergesort的遞歸給了我很大震動

小和問題是左邊的數在右邊找小和，

是以當

時，左指針p不動，

添進有序序列中，右指針自增

逆序對問題是右邊的數

在左邊找大的數

，

是以當

時，右指針q不動，

添進有序序列中，左指針自增

故這才有了在merge時的略微不同

SmallSum小和

//SmallSum
    while(p<=M&&q<=R)
	{
		sum+=(nums[p]<nums[q])?(R-q+1)*nums[p]:0;
		help[i++]=(nums[p]<nums[q])?nums[p++]:nums[q++];
	}
           

nixudv逆序對

//nixudv
    while(p<=M&&q<=R)
	{
		if(nums[p]>nums[q])sum+=M-p+1;
		help[i++]=(nums[p]<=nums[q])?nums[p++]:nums[q++];
	}
           

至于用對數器這件事，其實還是和之前插入排序的差不多，但這回驗證的不是序列中的每個元素，而是小數和/逆序對數是否相等。

即isequal用不到了，用的到的是新的函數，或者說一條if判斷語句

int right=rightMethod(nums1);
	    int test=testMethod(nums2);
	
        //if(!isequal(nums1,nums2))
		if(right!=test)
           

貼上原代碼 

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<windows.h>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;


int SmallSum_Ar(vector<int>&nums);

bool isequal(vector<int>&nums1,vector<int>&nums2)
{
	if(nums1.size()!=nums2.size())return 0;
	else return equal(nums1.begin(),nums1.end(),nums2.begin());
}

void generateRandomVector(vector<int>&nums1,int maxsize,int minvalue,int maxvalue)
{
	srand((unsigned int)(time(NULL)));
	int size=rand()%maxsize+1;//[1,maxsize]
	for(int i=0;i<size;i++)
	nums1.emplace(nums1.end(),(rand()%(maxvalue-minvalue+1)+minvalue));//[minvalue,maxvalue]
	return;
}

bool testAlgorithm(int (*rightMethod)(vector<int>&),int (*testMethod)(vector<int>&))
{
	
	srand((unsigned int)(time(NULL)));
	int maxsize =10,minvalue=-10,maxvalue=100;
	int testCount=rand()%10000+1 ,i=0;
	bool successflag=1;
		clock_t cur_clock;
	while(i<testCount)
	{
	vector<int>nums1,nums2,nums3;
	generateRandomVector(nums1,maxsize,minvalue,maxvalue);
	nums2=nums3=nums1;
	cur_clock=clock();
	int right=rightMethod(nums1);
	int test=testMethod(nums2);
	
//		if(!isequal(nums1,nums2))
		if(right!=test)
		{
			for(auto it=nums3.begin();it!=nums3.end();it++)
			printf("%d ",*it);
			successflag=0;
			return 0;
		}
		else successflag=1;
		
	i++;
	}
	if(successflag)
	printf("Nice After %f second",(double)(clock()-cur_clock)/(1000));
	return 1;
}

//小和問題 暴力法
int SmallSum_Ar(vector<int>&nums)
{
	int sum=0;
	for(int j=nums.size()-1;j>=1;j--)
	{
		int temp=0;
		for(int i=j-1;i>=0;i--)
		if(nums[j]>nums[i])temp+=nums[i];
		sum+=temp;
	}
	return sum;
}

int merge_SmallSum(vector<int>&nums,int L,int M,int R)
{
	vector<int>help(R-L+1);
	int p=L,q=M+1,i=0,sum=0;
	while(p<=M&&q<=R)
	{
		sum+=(nums[p]<nums[q])?(R-q+1)*nums[p]:0;
		help[i++]=(nums[p]<nums[q])?nums[p++]:nums[q++];
	}
	while(p<=M)help[i++]=nums[p++];
	while(q<=R)help[i++]=nums[q++];
	for(i=0;i<(int)help.size();i++)
	nums[L+i]=help[i];
	return sum;
}

int process_SmallSum(vector<int>&nums,int L,int R)
{
	if(L==R)return 0;
	int M=L+((R-L)>>1);
	return process_SmallSum(nums,L,M)+process_SmallSum(nums,M+1,R)+merge_SmallSum(nums,L,M,R);
}

int SmallSum(vector<int>&nums)
{
	if(nums.empty()||nums.size()==1)
	return 0;
	process_SmallSum(nums,0,nums.size()-1);
}



int merge_nixudv(vector<int>&nums,int L,int M,int R)
{
	vector<int>help(R-L+1);
	int p=L,q=M+1,i=0,sum=0;
	while(p<=M&&q<=R)
	{
		if(nums[p]>nums[q])sum+=M-p+1;
		help[i++]=(nums[p]<=nums[q])?nums[p++]:nums[q++];
	}
	while(p<=M)help[i++]=nums[p++];
	while(q<=R)help[i++]=nums[q++];
	for(i=0;i<(int)help.size();i++)
	nums[L+i]=help[i];
	return sum;
}

int process_nixudv(vector<int>&nums,int L,int R)
{
	if(L==R)return 0;
	int M=L+((R-L)>>1);
	return process_nixudv(nums,L,M)+process_nixudv(nums,M+1,R)+merge_nixudv(nums,L,M,R);
}

int nixudv(vector<int>&nums)
{
	if(nums.size()==1||nums.empty())return 0;
	return process_nixudv(nums,0,nums.size()-1);
}

int nixudv_right(vector<int>&nums)
{
	int len=nums.size()-1,sum=0;
	for(int i=len;i>=1;i--)
		for(int j=i-1;j>=0;j--)
			if(nums[i]<nums[j])sum+=1;
	return sum;
}
int main()
{
//	vector<int>v;int temp;
//	//https://blog.csdn.net/Vcrossover/article/details/106240862
//	while(cin>>temp)
//	{
//		v.push_back(temp);
//		if(cin.get()=='\n')
//		break;
//	}

//用對數器
	//test small-sum
//		testAlgorithm(SmallSum_Ar,SmallSum);
	//test nixudv
	testAlgorithm(nixudv_right,nixudv);
	
	
}