首页| JavaScript| HTML/CSS| Matlab| PHP| Python| Java| C/C++/VC++| C#| ASP| 其他|
购买积分 购买会员 激活码充值

您现在的位置是:虫虫源码 > 其他 > 统计逆序对

统计逆序对

  • 资源大小:233.64 kB
  • 上传时间:2021-06-30
  • 下载次数:0次
  • 浏览次数:0次
  • 资源积分:1积分
  • 标      签: 算法 c++ 统计 逆序

资 源 简 介

资源描述 Description 设a[0…n-1]是一个包含n个数的数组,若在ia[j],则称(i, j)为a数组的一个逆序对(inversion)。 比如 <2,3,8,6,1> 有5个逆序对。请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分元素大于右半部分元素的数量。 其中前两部分(1)和(2)由递归来实现。要保证算法最后效率O(nlogn),第三部分(3)应该如何实现? 此题请勿采用O(n^2)的简单枚举算法来实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中逆序对的个数有关系吗?什么关系? 输入格式 第一行:n,表示接下来要输入n个元素,n不超过10000。 第二行:n个元素序列。 输出格式 逆序对的个数。 输入样例 5 2 3 8 6 1 输出样例 5

文 件 列 表

11087.cpp
11087.exe
11087.o
VIP VIP
0.171751s