【PTA】归并排序 7-4 求逆序对数目 (20 分)

迷南。 2022-09-12 04:58 150阅读 0赞

**输入样例:**  
在这里给出一组输入。例如：

6
    -42 23 6 28 -100 65537
    结尾无空行

**输出样例:**  
在这里给出相应的输出。例如：

5
    结尾无空行

解答：

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1e4+5;
    int a[MAXN];
    int b[MAXN];
    int l,r,k;
    int ans=0;
    int Merge(int low,int mid,int high)
    {
        
    	l=low;r=mid+1;k=low;
    	while(l<=mid&&r<=high)
    	{
        
    		if(a[l]>a[r]) 
    		{
        
    			b[k++]=a[r++];
    			ans+= (mid-l+1);
    		}
    		else b[k++]=a[l++];
    	}
    	while(l<=mid) b[k++]=a[l++];
    	while(r<=high) b[k++]=a[r++];
    	
    	for(int i=low;i<=high;i++)
    	{
        
    		a[i]=b[i];
    	}
    }
    int mergesort(int low,int high)
    {
        
    	if(low>=high) return 0;
    	int mid=(low+high)/2;
    	mergesort(low,mid);
    	mergesort(mid+1,high);
    	Merge(low,mid,high);
    }
    int main()
    {
        
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    	}
    	mergesort(0,n-1);
    	cout<<ans;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1908 逆序对 (归并排序实现)

题目描述 > 猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之

朱雀/ 2023年05月29日 11:56/ 0 赞/ 234 阅读

相关求逆序对

题型: 编程题语言: 不限定 Description 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列

ゞ浴缸里的玫瑰/ 2023年02月11日 03:21/ 0 赞/ 19 阅读

相关数组中的逆序对（归并排序思想）

利用归并排序思想这题没有看懂，转来暂存 ![aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxODA1M

心已赠人/ 2023年01月02日 06:23/ 0 赞/ 207 阅读

相关【PTA】归并排序 7-4 求逆序对数目 (20 分)

输入样例: 在这里给出一组输入。例如： 6 -42 23 6 28 -100 65537 结尾无空行输出样例: 在这里给出相应的输出。例如

迷南。/ 2022年09月12日 04:58/ 0 赞/ 151 阅读

相关【日常学习】【归并逆序对】codevs1688 求逆序对题解

题目描述 Description 给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目数据范围：N<=105。Ai<

曾经终败给现在/ 2022年08月09日 12:48/ 0 赞/ 222 阅读

相关归并排序求逆序数

感觉还是数组用全局的比较快一些练习题目：[http://acm.hdu.edu.cn/showproblem.php?pid=4911][http_acm.hdu.edu.

短命女/ 2022年08月05日 08:56/ 0 赞/ 209 阅读

相关利用归并排序求逆序对

在逆序对的问题中，如果采用暴力求解的方法，一般也是有效的，但是O(n2)时间复杂度实在是难以接受的。但是对于逆序对问题，却有一个看似不想关的算法来解决–归并排序。时间复杂度和空

以你之姓@/ 2022年08月04日 15:40/ 0 赞/ 199 阅读

相关数据结构：归并排序 && 逆序对统计

归并排序要注意归并排序需要一个辅助空间，别的直接递归即可代码如下 include <iostream> include <vector>

╰半夏微凉°/ 2022年05月31日 12:53/ 0 赞/ 205 阅读

相关求逆序对数的方法(归并排序 and 树状数组)

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1

水深无声/ 2022年05月29日 06:24/ 0 赞/ 212 阅读

相关逆序对数目 java

逆序对数目 java 题目描述：设A\[1…n\]是一个包含n个两两不同数的数组。若在i<j的情况下，有A\[i\]>A\[j\]，则(i,j)称为A中的一个逆序对

偏执的太偏执、/ 2022年05月11日 14:33/ 0 赞/ 226 阅读