题目描述
说白了就是要求逆序对,这里记录两种做法,一个是使用归并排序求,这个y总在基本班讲过,还有一种是用树状数组来求。
树状数组思路
将输入的数按照大小关系排序,得到一个数组b,b中每个位置对应原数组(假设为a)这个数第几大,这应该也叫离散化吧QAQ,代码如下。
读入
// 自定义排序函数
bool cmp(const int x,const int y)
{
if(a[x] == a[y])
return x > y;
return a[x] > a[y];
}
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
b[i] = i;
}
sort(b + 1,b + 1 + n,cmp);
得到数组b过后,从前往后遍历,将 树状数组 b[i] 这个位置 + 1,然后 b[i] - 1 前面的和就是逆序对的数量,一直累加即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 500010;
int a[N],b[N];
long long c[N];
int n;
long long ans;
bool cmp(const int x,const int y)
{
if(a[x] == a[y])
return x > y;
return a[x] > a[y];
}
inline int lowbit(int x){return x & -x;}
int add(int x,int v)
{
for(; x < N; x += lowbit(x)) c[x] += v;
}
long long ask(int x)
{
long long ret = 0;
for(; x ; x -= lowbit(x)) ret += c[x];
return ret;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(c,0,sizeof c);
ans = 0;
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
b[i] = i;
}
sort(b + 1,b + 1 + n,cmp);
for(int i = 1; i <= n; i ++)
{
add(b[i],1);
ans += ask(b[i] - 1);
}
printf("%lld\n",ans);
}
}
归并做法
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 500010;
int a[N],tmp[N];
int n;
long long ans;
void merge_sort(int l,int r)
{
if(l >= r) return ;
int mid = l + r >> 1;
merge_sort(l,mid),merge_sort(mid + 1,r);
int i = l, j = mid + 1,cnt = 0;
while(i <= mid && j <= r)
{
if(a[i] > a[j])
{
tmp[++ cnt] = a[j++];
ans += mid - i + 1;
}
else tmp[++ cnt] = a[i ++];
}
while(i <= mid) tmp[++ cnt] = a[i ++];
while(j <= r) tmp[++ cnt] = a[j ++];
for(int i = l,j = 1; i <= r; i ++,j ++) a[i] = tmp[j];
}
int main()
{
while(scanf("%d",&n),n)
{
ans = 0;
for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);
merge_sort(1,n);
printf("%lld\n",ans);
}
}