首页 > 代码库 > poj 2299 Ultra-QuickSort 归并排序解法
poj 2299 Ultra-QuickSort 归并排序解法
点击打开链接题目链接
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 42347 | Accepted: 15389 |
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.
Ultra-QuickSort produces the output
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.
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
要求求出冒泡排序的交换次数
可以用归并排序求出逆序数然后做
代码:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int MAXN=500010; __int64 t; int num[MAXN],R[MAXN]; void merco(int l,int mid,int r) { int i=l,j=mid+1,p=0; while(i<=mid&&j<=r) { if(R[i]<=R[j]) { num[p++]=R[i++]; } else { num[p++]=R[j++]; t+=(mid-i+1); } } while(i<=mid) { num[p++]=R[i++]; } while(j<=r) { num[p++]=R[j++]; } for(i=0;i<p;i++) { R[l+i]=num[i]; } } void mer(int l,int r) { int mid=(l+r)>>1; if(l<r) { mer(l,mid); mer(mid+1,r); merco(l,mid,r); } } int main() { int n,i; while(scanf("%d",&n)!=EOF&&n) { t=0; for(i=0;i<n;i++) { scanf("%d",&R[i]); } mer(0,n-1); printf("%I64d\n",t); } return 0; }
poj 2299 Ultra-QuickSort 归并排序解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。