NYOJ 117 求逆序数 （树状数组 + 离散化思路）
发布时间
阅读量：
阅读量
求逆序数
时间限制： 2000 ms | 内存限制： 65535 KB
难度： 5
描述
在一个排列中任取两个元素，在其相对位置与其数值大小相反的情况下，则称这对元素为一个逆序；该排列中所有这样的有序对的数量即被定义为该排列的逆序总数
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
请用户输入一个整数值T作为测试数据组的数量（1到5之间）。对于每个测试用例而言，在每一行中将有一个整数值N来标识该序列包含的具体元素数量（2到一百万之间）。在接下来的一行中将会有正好N个整数值Ai（其中每个Ai满足条件：小于十亿），这些数值构成了整个序列的所有元素。
数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出 输出该数列的逆序数
样例输入
样例输出
为了实现将数值映射至相应位置的任务，
为了解决数值过于分散且规模较大的问题，
我们可以采取以下步骤：
首先，
将每个数值及其对应的位置信息存储于结构体数组中；
接着，
按数值大小进行排序；
然后，
采用连续整数序列1,2,3,…依次替代原有数值；
最后，
随后将reflect数组以逆序方式插入到树状数组中；
每一步骤完成后，
计算当前插入点之前所有已存在的节点之和，
这一步骤等价于求取当前节点在已处理节点中所处的位置排名，
从而得到该节点在整个序列中的逆序数目。
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int tree[1000005];
int reflect[1000005];
int n;
struct node
{
int val;
int pos;
}a[1000005];
bool cmp(node n1, node n2)
{
if(n1.val != n2.val)
return n1.val < n2.val;
return n1.pos < n2.pos;
}
void add(int k, int num)
{
while(k <= n)
{
tree[k] += num;
k += k & -k;
}
}
long long query(int k)
{
int sum = 0;
while(k >= 1)
{
sum += tree[k];
k -= k & -k;
}
return sum;
}
int main()
{
int T, i, j;
long long sum;
cin >> T;
while(T --)
{
cin >> n;
sum = 0;
memset(tree, 0, sizeof(tree));
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i].val);
a[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);//离散化，将数组按值从小到大排列
for(i = 1; i <= n; i++)
{
reflect[i] = a[i].pos;//映射数组，从值到位置的映射
}
for(i = n; i >= 1; i--)//将数从大到小添加，每添加一个数，求该数前面有多少个数，
{
add(reflect[i], 1);
sum += query(reflect[i]) - 1;//-1是除去该数本身
}
cout << sum <<endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~