首页 > 其他 > 详细

洛谷 P1908 逆序对

时间:2019-02-23 15:21:17      阅读:165      评论:0      收藏:0      [点我收藏+]

嗯...

 

首先我们先看一下这个题,这可以说是一个归并排序的模板(与归并排序只有ans一个地方差距....

 

如果你还不知道归并排序这个东西,请看下面的网址,这是我以前写的一个归并排序的一个模板..

 

https://www.cnblogs.com/New-ljx/p/10363132.html

 

接着回到逆序对这道题中:

 

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。

最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。

知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。Update:数据已加强。

输入输出格式

输入格式:

 

第一行,一个数n,表示序列中有n个数。

第二行n个数,表示给定的序列。序列中每个数字不超过10^9109

 

输出格式:

 

给定序列中逆序对的数目。

 

输入输出样例

输入样例#1:
6
5 4 2 6 3 1
输出样例#1:
11

说明

对于25%的数据,n2500

对于50%的数据,10^4n4×104。

对于所有数据,10^5n5×105

请使用较快的输入输出

应该不会n方过50万吧 by chen_zhe

 

解析:

嗯...这道题吧,其实就是求逆序对个数,即为求序列中ai>aj且i<j的有序对,这其实就是一个归并排序的一个模板...

思路就是在归并排序(分治思想)中比较前面的数与后面数的大小,用ans 这个东西来存储最后的答案...

 

 

详细请见AC 代码:

 

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn = 5e5+5;
 4 int n, a[maxn], t[maxn]; //a数组用来输入,t数组用来备份存储最后的有序列 
 5 long long ans;//存储逆序对个数 
 6 void merge(int l, int r) {//归并排序 
 7     if(l == r) return ;
 8     int mid = l + (r - l)/2;//每次求区间中间 
 9     merge(l,mid); merge(mid+1,r);//递归分解,分治思想 
10     int k = l, o = l,j = mid + 1;//将左端点、右端点、中点记录下来 
11     while(o <= mid && j <= r) {//排序过程,划定边界 
12         if(a[o] <= a[j]) t[k++] = a[o++];//取较小的存入t
13         else  t[k++] = a[j++] , ans += (long long)mid - o + 1;//如果满足逆序对,则也将较小的一个入t数组,并且将逆序对个数加入 
14         /*对上一语句更详细地解释:
15         因为每一块都是已经按从小到大进行排序,如果前面有一个与后面的点构成了逆序对,
16         那么这一个的后面所有的点(在一定范围内 mid - o + 1 ),即都与后面的那个点构
17         成逆序对,可以进行优化...*/ 
18     }
19     while(o <= mid) t[k++] = a[o++];//将剩余元素推入有序序列(剩余元素皆为序列最大值) 
20     while(j <= r) t[k++] = a[j++];//同上 
21     for(k = l; k <= r; k++) a[k] = t[k];//复制回a数组中 
22 }
23 int main()
24 {
25     scanf("%d",&n);
26     for(int k = 1;k <= n; k++) scanf("%d",&a[k]);
27     merge(1, n);
28     printf("%lld",ans);
29 
30 return 0;
31 }

 

就是这个样....

 

洛谷 P1908 逆序对

原文:https://www.cnblogs.com/New-ljx/p/10422688.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!