题目是快速排序,可用的居然是合并排序,排序中计算逆序数即可。。。
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long int count;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Merge(long long int a[],long long int p,long long int k,long long int q)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long long int num1=k-p+1;
long long int num2=q-k;
long long int i;
long long int* b1=new long long int[num1+1];
long long int* b2=new long long int[num2+1];
for (i=0;i<num1;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
b1[i]=a[p+i];
}
b1[i]=9999999999;
for (i=0;i<num2;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
b2[i]=a[k+i+1];
}
b2[i]=9999999999;
int j=0;i=0;
for(long long int kk=p;kk<=q;kk++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (b1[i]<=b2[j])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
a[kk]=b1[i];
i++;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
a[kk]=b2[j];
j++;
count+=(num1-i); //求逆序数,即若b中有元素比a小,插入后共有a数组大小减去当前指向a的位置个逆序
}
}
delete [] b1;
delete [] b2;
}
void MergeSort(long long int a[],long long int p,long long int q)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if (p<q)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long long int k=(p+q)/2;
MergeSort(a,p,k);
MergeSort(a,k+1,q);
Merge(a,p,k,q);
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long int num;
while (scanf("%ld",&num)!=EOF&&num)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long long int* input=new long long int[num];
count=0;
for (int i=0;i<num;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%lld",&input[i]);
}
MergeSort(input,0,num-1);
printf("%lld\n",count);
delete [] input;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)