逆序对是这样定义的:对于给定的一段正整数序列,逆序对就是序列中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