Ultra-QuickSort - poj 2299 (归并排序+统计逆序数)
2024-09-03 20:08:42
利用归并排序统计逆序数,利用归并求逆序在对子序列s1和s2在归并时(s1,s2已经排好序),若s1[i]>s2[j](逆序状况),则逆序数加上s1.length-i,因为s1中i后面的数字对于s2[j]都是逆序的。
#include <stdio.h>
#include <stdlib.h>
int N;
int num[];
int tmp[];
__int64 count;
void Merge(int l,int mid,int r){
int i=l,j=mid+,k=;
while(i<=mid&&j<=r){
if(num[i]>num[j]) {
tmp[k++]=num[j++];
count+=mid-i+;
} else
{
tmp[k++]=num[i++];
}
}
while(i<=mid) tmp[k++]=num[i++];
while(j<=r) tmp[k++]=num[j++]; for(i=; i<k; i++)
{
num[l+i]=tmp[i];
}
}
void Mergesort(int l,int r){
int mid=(l+r)/;
if(l<r){
Mergesort(l,mid);
Mergesort(mid+,r);
Merge(l,mid,r);
}
}
int main(void) {
scanf("%d",&N);
int i=;
while(N){
for(i=;i<N;i++){
scanf("%d",&num[i]);
}
count=;
Mergesort(,N-);
printf("%I64d \n",count);
scanf("%d",&N);
} return EXIT_SUCCESS;
}
附:
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 48082 | Accepted: 17536 |
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
最新文章
- source tree 推送错误解决
- 非阻塞同步算法实战(三)-LatestResultsProvider
- 39-tar 打包压缩
- 9.5---括号是否有效(CC150)
- Replace INTO与INSERT INTO的不同之处
- nginx 安全漏洞 (CVE-2013-4547)
- uboot的mkconfig分析
- java设计模式---原型模式
- Collection使用方法
- Linux中的读函数与块高速缓存
- silverlight控件动画状态的过渡
- 通过配置Windows 防火墙允许使用TCP/IP协议远程访问数据库
- Inno Setup 网页显示插件 webctrl
- DEAMONTOOLS: installation
- vuex脑图
- 关于使用format()方法格式化字符串,读这一篇就够了!
- CentOS 7.5 安装KVM虚拟机(Linux)
- 将打印(printk/printf)及时写入文件的方法
- 无监督学习——K-均值聚类算法对未标注数据分组
- 在Unity3d中调用外部程序及批处理文件
热门文章
- canvas的一些问题记录
- DOM系统学习-表格、样式和元素大小
- ClipboardJS复制粘贴插件的使用
- 基于CentOS与VmwareStation10搭建Oracle11G RAC 64集群环境:3.安装Oracle RAC-3.6.集群管理命令
- Spark Streaming从Flume Poll数据案例实战和内幕源码解密
- Android架构分析之Android消息处理机制(一)
- iOS-国家代码选择功能github开源分享
- Android笔记:invalidate()和postInvalidate() 的区别及使用——刷新ui
- android 调用系统界面
- 【Python3 爬虫】10_Beautiful Soup库的使用