数据结构 nxd(顺序对)
问题描述
给定 n 个数 a1,a2,...,an，求满足条件的(i,j)数量： i<j 且 a[i]<a[j]
★数据输入
输入第一行为一个正整数 n。
第二行为 n 个数，第 i 个代表 ai。
对于 90%的数据， 1<=n<=6666;
对于 100%的数据， 1<=n<=100086， 0<=ai<=1000,000,000;
★数据输出
输出满足条件的（i, j） 的数量。
| 输入示例 | 输出示例 |
| 5 9 1 5 2 2 |
3 |
| 输入示例 | 输出示例 |
| 7 4 3 1 5 5 5 2 |
10 |
解题思路
解法1：
插入排序，二分查找
c++可用vector + lower_bound实现
注意 100086^2 = 100亿+，结果应用__int64 (long long int) 存
解法2：
手写归并排序，从大到小排列，统计数据左移次数
code
解法1
#include <stdio.h>
#include <iostream> class A
{
public:
A(int _maxsize)
:ans(),size()
{
arr = new int[_maxsize+];
}
~A()
{
delete arr;
}
void insert(int n)
{
int pos = findInsertPos(n);
ans += pos;
for(i=size;i>pos;i--)
{
arr[i] = arr[i-];
}
arr[pos] = n;
size++;
}
__int64 getAns()
{
return ans;
}
void _disAll()
{
for(i=;i<size;i++)
printf("%d ",arr[i]);
printf("\n");
}
private:
int findInsertPos(int n)
{
if(size==)
{
return ;
}
else if(n <= arr[])
{
return ;
}
else if(n>arr[size-])
{
return size;
}
else
{
int l=,r=size-,mid=(l+r)/;
for( ; l<r ; mid=(l+r)/)
{
if(arr[mid]<n && n<=arr[mid+])
{
return mid+;
}
else if(n>arr[mid])
{
l=mid;
}
else// if(arr[mid]>n)
{
r=mid;
}
}
// printf("error! no found\n");
return ;
}
}
private:
__int64 ans;
int *arr;
int size;
int i,j;
}; int main()
{
// freopen("in.txt","r",stdin);
int n,i,buf;
scanf("%d",&n);
A obj(n);
for(i=;i<n;i++)
{
scanf("%d",&buf);
obj.insert(buf);
// obj._disAll();//tester
}
printf("%I64d",obj.getAns()); return ;
}
解法2
#include <stdio.h>
#include <stdlib.h> __int64 ans=;
int *arr=NULL,*buf=NULL;
int len=; void init()
{
ans=;
int i;
scanf("%d",&len);
arr = (int *)malloc(sizeof(int)*len);
buf = (int *)malloc(sizeof(int)*len);
for(i=;i<len;i++)
scanf("%d",arr+i); }
void disAll();
void mergeSort(int *p, int l, int r)//归并 从大到小
{
if(l>=r) return;
if(r==l+)
{
if(p[l]<p[r])
{
p[l]^=p[r];
p[r]^=p[l];
p[l]^=p[r];
ans++;//
}
}
else
{
int m = (l+r)/;
mergeSort(p,l,m);
mergeSort(p,m+,r); int i,j,k;
for(i=l;i<=r;i++)
buf[i]=p[i];
for(k=l,i=l,j=m+;k<=r;)
{
if(i>m)
p[k++] = buf[j++];
else if(j>r)
p[k++] = buf[i++];
else if(buf[i]>=buf[j])
p[k++] = buf[i++];
else// if(buf[j]>buf[i])
{
ans+=m+-i;//
p[k++] = buf[j++];
}
}
}
} void deleteAll()
{
if(arr) free(arr);
if(buf) free(buf);
} void disAns()
{
printf("%I64d",ans);
} void _disAll()
{
for(int i=;i<len;i++)
printf("%d ",arr[i]);
printf("\n");
} int main()
{
init();
mergeSort(arr,,len-);
disAns(); deleteAll();
return ;
}