POJ2299+逆序数
2024-10-10 22:54:26
归并排序!!!!!!!!!!
/*
归并排序+求逆序数
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
typedef __int64 int64;
const int maxn = ;
int64 a[ maxn ],Sort[ maxn ];
int64 res; void init(){
res = ;
} void merge( int L,int R ){
int mid = (L+R)/;
int i = L;
int j = mid+;
int pos = L;
while( i<=mid&&j<=R ){
if( a[i]<a[j] )
Sort[ pos++ ] = a[i++];
else{
Sort[ pos++ ] = a[j++];
res += (mid-i+);
}
}
while( i<=mid )
Sort[ pos++ ] = a[i++];
while( j<=R )
Sort[ pos++ ] = a[j++];
for( int k=L;k<=R;k++ )
a[k] = Sort[k];
} void merge_sort( int L,int R ){
int mid = (L+R)/;
if( L<R ){
merge_sort( L,mid );
merge_sort( mid+,R );
merge( L,R );
}
return ;
} int main(){
int n;
while( scanf("%d",&n),n ){
for( int i=;i<=n;i++ )
scanf("%I64d",&a[i]);
init();
merge_sort( ,n );
printf("%I64d\n",res);
}
return ;
}
最新文章
- ELK:kibana使用的lucene查询语法【转载】
- spark新能优化之提高并行度
- 二十一、contextMap中放的常用数据
- [ExtJS5学习笔记]第三十六节 报表组件mzPivotGrid
- 【Linux】【MySQL】CentOS7、MySQL8.0.13 骚操作速查笔记——专治各种忘词水土不服
- keepalived+nginx实现niginx高可用,宕机自动重启
- ubuntu vscode chrome 显示color emoji
- GitHub 教程【转】
- Nginx安装部署以及配置文件解析
- 快速链接bioconductor,以及安装“XML”
- P2043 质因子分解
- kubernetes yaml
- 十七 能停止的线程 暴力停止 和 interrupt/return方法
- VC中_T()的作用
- Linux下如何将文件下载到指定目录
- oracle数据库之存储函数和过程
- joomla 出现The file Cache Storage is not supported on this platform;
- 【luogu P3063 [USACO12DEC]牛奶的路由Milk Routing】 题解
- 10道典型的JavaScript面试题
- hive 导入csv文件