时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个1-N的排列A1, A2, ... AN，如果Ai和Aj满足i < j且Ai > Aj，我们就称(Ai, Aj)是一个逆序对。
求A1, A2 ... AN中所有逆序对的数目。
输入
第一行包含一个整数N。
第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)
对于60%的数据 1 <= N <= 1000
对于100%的数据 1 <= N <= 100000
输出
一个整数代表答案
- 样例输入
-
5
3 2 4 5 1 - 样例输出
-
5
求逆序对，两种方法，一个是用树形数组做，一个是用归并排序做。两种都试了一遍，有一个地方比较坑就是数组类型必须是long long。不然会WA，题目却没有明显信息说要long long。。这个地方可以说是很坏坏了。
树形数组ac代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std; //1524 : 逆序对
const int maxn = 1e5 + ;
int n;
long long a[maxn], b[maxn];
int lowbit(int i)
{
return i&-i;
}
void update(int i)
{
while (i <= n)
{
b[i]++;
i += lowbit(i);
}
}
long long sum(int i)
{
long long cnt = ;
while (i)
{
cnt += b[i];
i -= lowbit(i);
}
return cnt;
}
int main()
{
cin >> n;
for (int i = ;i <= n;i++)
{
cin >> a[i];
}
memset(b, , sizeof(b));
long long res = ;
for (int i = n;i >= ;i--)
{
update(a[i]);
res += sum(a[i] - );
}
cout << res << endl;
return ;
}
树形数组这个东西还是比较有趣的。这个算法可以说是比较天才了。
具体的树形数组详解可以看这个博主的http://blog.csdn.net/ljd4305/article/details/10101535
归并排序的ac代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std; //1524 : 逆序对
const int maxn = 1e5 + ;
int n;
long long a[maxn],b[maxn];
long long cnt; void merge_sort(long long * a, int l, int r)
{
int mid = (l + r) >> ;
int m = l, n = mid + ;
int pos = l;
while (m<=mid&&n<=r)
{
if (a[m] < a[n])
{
b[pos++] = a[m++];
}
else
{
b[pos++] = a[n++];
cnt+=mid-m+;
}
} while (m <= mid) b[pos++] = a[m++];
while (n <= r) b[pos++] = a[n++];
for (int i = l;i <= r;i++)
a[i] = b[i];
}
void merge(long long * a, int l, int r)
{
if (l >= r) return;
int mid = (l + r) >>;
merge(a, l, mid);
merge(a, mid+, r);
merge_sort(a, l, r);
} int main()
{
cnt = ;
cin >> n;
for (int i = ;i <= n;i++)
{
cin >> a[i];
}
merge(a, , n);
cout << cnt << endl;
return ;
}
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数。
可以参考http://blog.csdn.net/acdreamers/article/details/16849761