博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
openjudge 7622 求排列的逆序数(归并)
阅读量:6820 次
发布时间:2019-06-26

本文共 1232 字,大约阅读时间需要 4 分钟。

总时间限制:  1000ms   内存限制:  65536kB
描述

在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1,i2,…,in,如果其中存在j,k,满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。显然,由1,2,…,n 构成的所有n!个排列中,最小的逆序数是0,对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列,求它的逆序数。

输入
第一行是一个整数n,表示该排列有n个数(n <= 100000)。
第二行是n个不同的正整数,之间以空格隔开,表示该排列。
输出
输出该排列的逆序数。
样例输入
62 6 3 4 5 1
样例输出
8
提示
1. 利用二分归并排序算法(分治);
2. 注意结果可能超过int的范围,需要用long long存储。

解题思路:

  归并排序,若遇到后面的数比前面的小时,逆序对数量为当前位置减去已排好的位置差。

 

#include
#include
#include
using namespace std;typedef long long ll;const int N = 100000+10;int a[N],temp[N];ll ans=0;void Merge(int l,int m,int r){ int i=l,j=m+1,pos=l; while(i<=m&&j<=r){ if (a[i]
=r) return; MergeSort(l,mid); MergeSort(mid+1,r); Merge(l,mid,r);}int main(){ int n,m; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); MergeSort(1,n); printf("%lld\n",ans); return 0;}
View Code

 

转载于:https://www.cnblogs.com/l999q/p/10349149.html

你可能感兴趣的文章
使用xtrabackup备份mysql8.0.16
查看>>
安装apache遇到的几个错误及解决办法 [error] Apache2.2: Service is already installed.
查看>>
Spring Security源码分析一:Spring Security认证过程
查看>>
Dubbo环境搭建
查看>>
[数据结构]插入排序与希尔排序
查看>>
如何高效利用GitHub
查看>>
Server-sent Event 简单介绍
查看>>
nginx 常用的几个命令
查看>>
解决命令行的乱码以及编码的问题
查看>>
Linux 程序获取环境变量
查看>>
vim设置括号自动补全
查看>>
windows环境eclipse开发C++程序
查看>>
svn 常用命令总结
查看>>
Tomcat全攻略
查看>>
make: *** linux-2.6.36.4/arch/arm: Is a directo...
查看>>
android http连接阻塞超时问题
查看>>
异常处理
查看>>
线性插值针对位置量和角度量
查看>>
关于方法快的理解
查看>>
sublime text2配置
查看>>