Ultra-QuickSort(归并排序求逆序对数)
2024-08-27 02:14:39
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 34283 | Accepted: 12295 |
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.
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.
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
//归并排序模板,只加了一句 cnt += m-p;
#include<stdio.h>
#include<string.h>
long long cnt;
int num[],tmp[];
void merge_sort(int num[],int x, int y, int tmp[])
{
if(y-x > )
{
int m = x + (y-x)/;
int p = x, q = m, i = x;
merge_sort(num,x,m,tmp);
merge_sort(num,m,y,tmp);
while(p < m || q < y)
{
if(q >= y || (p < m && num[p] <= num[q]))
tmp[i++] = num[p++];
else
{
tmp[i++] = num[q++];
cnt += m-p;
}
}
for(i = x; i < y; i++)
num[i] = tmp[i];
}
}
int main()
{
int n;
while(~scanf("%d",&n) && n)
{
for(int i = ; i < n; i++)
scanf("%d",&num[i]);
cnt = ;
merge_sort(num,,n,tmp);
printf("%I64d\n",cnt);
}
return ;
}
最新文章
- 扩展JS Date对象时间格式化功能
- MySQL GROUP_CONCAT函数使用示例:如何用一个SQL查询出一个班级各个学科第N名是谁?
- ..c++中用c语言的输入法
- angularjs2 学习笔记(四) 路由
- abstract
- 使用HttpServletRequestWrapper在filter修改request参数
- HMM模型详解
- PHP memcache实现消息队列实例
- PHP测试题讲解(20161027)
- docker应用笔记
- MySQL 笔记整理(6) --全局锁和表锁:给表加个字段怎么有这么多阻碍
- Python爬虫实战一之爬取QQ音乐
- React生命周期简单详细理解
- Socket的长连接和短连接
- pytorch之LSTM
- C++学习笔记(原创)
- SeekBar的用法和自定义滑块的样式
- Verilog篇(三)仿真原理
- 【转】Linux进程绑CPU核
- environment variable is too large 2047
热门文章
- POJ3169 Layout(差分约束系统)
- POJ 2075 Tangled in Cables (c++/java)
- [Javascript] Proper use of console.assert in JavaScript
- 如何使用Valgrind memcheck工具进行C/C++的内存泄漏检测
- navicat导入mysql数据库sql时报错或数据不完全问题
- Day7 - Python基础7 面向对象编程进阶
- XML在JAVA项目中的作用
- css.day04
- javaee后台适合用的编辑器插件
- .NET读取Excel