首页 > 代码库 > 归并排序&&逆序对(codves1688,4163)
归并排序&&逆序对(codves1688,4163)
归并排序
归并排序采用的是分治的思想
1、划分问题:把序列分为元素个数尽量相等的两半
2、递归求解:把两半分别排序
3、合并问题:把两个有序的序列合并为一个
对于第三个问题,我们可以从两个序列中最小的元素开始比较,把较小的加入新的队列中,直到某个序列为空,把另外的一个序列直接加入,然后将原来的序列覆盖。其实很简单,下面看看模板代码
写得烂,不要在意(⊙o⊙)…;
这个就是归并排序(⊙o⊙)…,本人感觉很简单的,归并排序好像比sort,快排的复杂度低,也就是说快一点,是NlogN的复杂度。既然说了归并排序,就不得不说下逆序对如codevs 1688 模板题
1688 求逆序对
题目描述 Description
给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目
!!!!!!数据范围:N<=105。Ai<=105。时间限制为1s。//注意这里范围
输入描述 Input Description
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
对于逆序对如果范围小,可以用冒泡排序,交换一次ans++;最后排好了答案就出来了。但是冒泡排序是O(n^2)的复杂度,一看数据范围是1e5
就知道要超时。所以就用归并排序,来实现问题。其实只需要加一句代码就行了
加上这句就完啦,最后输出ans就可以了。
为什么是加mid-q+1呢?
我们在进行合并的时候是从小到大进行的,就是说,当把右段的数x放到临时数组t中的时候,左段的数一定比x都大,有mid-p+1个,这些数一定都和x成逆序对,因为他们的位置在x前,而值比x大。
这就是逆序对的解法。
归并排序&&逆序对(codves1688,4163)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。