POJ训练计划2299_Ultra-QuickSort(归并排序求逆序数)
2024-10-01 07:56:27
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 39279 | Accepted: 14163 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence
element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
Source
解题报告
求相邻的两两交换排序要几个步骤,就是求逆序数。
求逆序数的n方算法肯定超时,网上介绍了高速求逆序数的算法是用归并排序来实现的,时间复杂度是O(nlogn)。
刚学习了归并排序,这里不介绍归并排序。
为什么归并排序能够求逆序数。
在一个排列中,假设一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。依据归并排序,“划分”把序列分成元素个数尽量相等的两半,“递归”统计i和j均在左边或是均在右边的逆序对个数;“合并”统计i在左边,但j在右边的逆序数个数。
怎么统计逆序数个数呢?在归并排序合并操作时,因为是从小到大的排序,当A[j]复杂到T中时,左边还没有来得及复制的那些数就是左边全部比A[j]大的数。(以上i表示左区间数组的指针,j表示右区间数组指针,T是辅助空间,A是原数组)
这个题目要注意的是复杂空间必须开全局,局部可能溢出,还有答案要用longlong存。
#include <iostream> using namespace std;
long long a[500010],t[500010],cnt=0;
void gbsort(long long *a,long long l,long long r)
{
if(l<r)
{
long long mid=(l+r)/2;
gbsort(a,l,mid);
gbsort(a,mid+1,r);
long long s=l,e=mid+1;
long p=0; while(s<=mid&&e<=r)
{
if(a[s]<=a[e])
{
t[p++]=a[s++];
}
else
{
t[p++]=a[e++];
cnt+=mid-s+1;
}
}
while(s<=mid)
{
t[p++]=a[s++];
}
while(e<=l)
{
t[p++]=a[e++];
}
for(int i=0;i<p;i++)
a[l+i]=t[i];
}
}
int main()
{
int n;
while(cin>>n)
{
if(!n)break;
cnt=0;
for(int i=0; i<n; i++)
cin>>a[i];
gbsort(a,0,n-1);
cout<<cnt<<endl;
}
return 0;
}
最新文章
- Android应用中实现系统“分享”接口
- Android Lint Checks
- 简述SQL2008部署多实例集群(学习)
- Apache Shiro系列二,概述 —— 基本概念
- IIS ARR 负载均衡
- mybatis 添加事物后 无法获取自增主键的问题
- Hive history date mapping
- mysql一次添加多条记录
- 关于$.fn
- 服务器放在不同省份的IDC机房,数据如何同步?一个域名如何动态解析到不同IP的服务器
- HDU 1248 冰封王座(dp)
- [转载] 关于Windows Boot Manager、Bootmgfw.efi、Bootx64.efi、bcdboot.exe 的详解
- HDU 1589 Find The Most Comfortable Road 最小生成树+枚举
- Quick Cocos2dx 场景对象基类实现
- Vue 非父子组件通信
- HiveSchemaTool-Parsing failed. Reason- Unrecognized option- -dbType&#160;mysql
- openldap 搭建
- PowerDesigner设置Oracle不区分大小写
- [Tools] Wireshark Primer Tutorials
- 模仿jdk编译代码去除注释,多行注释