逆序对_数组中的逆序对

逆序对_数组中的逆序对逆序对是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。 说人话,就是一个数列中,一个数在你后面,去比你小,则这俩数就是一对逆序对。 怎么做呢?常规的算法是开一个结构体,记录每一个数的值和他在数组中的位置。然后按值从小到大排序。 在开一个标记数组,从1到

逆序对_数组中的逆序对"

逆序对是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。

 

说人话,就是一个数列中,一个数在你后面,去比你小,则这俩数就是一对逆序对。

 

怎么做呢?常规的算法是开一个结构体,记录每一个数的值和他在数组中的位置。然后按值从小到大排序。

在开一个标记数组,从1到n循环,对于排好序的数组中的元素i,将其对应的位置i.id标记成1,然后统计一下这个位置后面有多少个1,就是和这个数搭配的逆序对数。

可以这么理解,因为是越小的的数就越先去标记,所以对于一个数 i,比他小的数一定先标记过了,那么在i位置后面的标记一定满足既比他小,位置又比他靠后,不就是逆序对嘛。

 

而统计在他后面的标记有多少个,就可以用树状数组实现,单点修改,后缀查询。不过习惯是查询前缀,那只要改成从n到1循环就行了(当然从大到小排序也可以)。

 

不过这还没完,因为要考虑数字相同的情况。

比如1 1 1 1 1,逆序对数是0,但是我们排序的时候没有定义值相同的时候怎么排,是未定义行为,结果就不知道是啥了。

所以要考虑的是,值相同时,是位置靠前的排在前面,还是位置靠后的排在前面。

可以试验一下

若是值靠前的排在前面,那么上述排序结果是1 2 3 4 5,然后从n到1循环。先是a[5],就vis[5] = 1,统计一下后面,是0;然后a[4],则vis[4] = 1,统计后面被标记的,发现是1;a[3],vis[3] = 1,ans += 2……这么循环下去,答案就是1 + 2 + 3 + 4= 10,很显然错了。

 

再试一下位置靠后的排在前面,那么排序结果5 4 3 2 1,从5开始,vis[1] = 1,ans + 0;a[2], vis[2] = 1,ans += 0;a[3], vis[3] = 1,ans += 0……这样下去答案一直就是0了,对了。

 

所以这么做的话,就应该在值相同的情况下,位置靠后的排在前面。但这却不绝对,只是因为这种写法,若是从大到小循环就不一定了,感兴趣的可以自己试验一下。

给出一种写法

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 #define rep(i ,a, n) for(int i = a; i <= n; ++i)
 7 #define per(i, n, a) for(int i = n; i >= a; --i)
 8 typedef long long ll;
 9 const int maxn = 4e4 + 5;
10 struct Node
11 {
12     int num, id;
13     bool operator < (const Node& other)const
14     {
15         return num < other.num || (num == other.num && id < other.id);
16     }
17 }a[maxn];
18 int c[maxn], n;
19 int ans = 0;
20 int lowbit(int x)
21 {
22     return x & -x;
23 }
24 void add(int pos, int w)
25 {
26     while(pos <= n)
27     {
28         c[pos] += w;
29         pos += lowbit(pos);
30     }
31 }
32 int sum(int pos)
33 {
34     int ret = 0;
35     while(pos > 0)
36     {
37         ret += c[pos];
38         pos -= lowbit(pos);
39     }
40     return ret;
41 }
42 int main()
43 {
44     scanf("%d", &n);
45     rep(i, 1, n) {scanf("%d", &a[i].num); a[i].id = i;}
46     sort(a + 1, a + n + 1);
47     per(i, n, 1)
48     {
49         ans += sum(a[i].id);
50         add(a[i].id, 1);
51     }
52     printf("%d\n", ans);
53     return 0;
54 }

 

 

上述是一种比较常见的思路,就是按数值大小的顺序插入到对应的位置中。其实也可以按位置的前后插入到对应的大小顺序中。这两种效果相同。

 

 

——————————————-18.5.19更新——————————————

 

这天又做了一道逆序对的题,然后想出了一个更简洁的算法,不用结构体,不用sort。

 

首先也是要开一个类似于vis[]的数组,vis[x]记录x出现的次数。然后我们从头开始把vis[a[i]]++,这样对于每一次查询a[i]的逆序对,我们只用看位于a[i]后面的已经标记的数有多少个,a[i] + 1的后缀和,因为a[i]后面已经标记的数代表了比a[i]更早出现却比a[i]大的数,就是逆序对的定义嘛。

 

于是我想用树状数组,但树状数组是求动态前缀和的。于是我就改成了a[i]从后往前插入,这样就把后缀和改成了前缀和。

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn = 1e5 + 5; 
 7 int n, a[maxn], c[maxn];
 8 int lowbit(int x)
 9 {
10     return x & -x;
11 }
12 void add(int x, int d)
13 {
14     int pos = x;
15     while(pos < maxn)
16     {
17         c[pos] += d;
18         pos += lowbit(pos);
19     }
20 }
21 int sum(int x)
22 {
23     int pos = x, ret = 0;
24     while(pos > 0)
25     {
26         ret += c[pos];
27         pos -= lowbit(pos);
28     }
29     return ret;
30 }
31 ll ans = 0;
32 int main()
33 {
34     scanf("%d", &n); 
35     for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
36     for(int i = n; i >= 1; --i)
37     {
38         ans += sum(a[i] - 1);
39         add(a[i], 1);
40     }
41     printf("%lld\n", ans);
42     return 0; 
43 }

 

今天的文章逆序对_数组中的逆序对分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/47038.html

(0)
编程小号编程小号
上一篇 2023-09-05 09:17
下一篇 2023-09-05

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注