Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 39279 | Accepted: 14163 |
Description
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
element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
Source
#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;
}
POJ训练计划2299_Ultra-QuickSort(归并排序求逆序数)的更多相关文章
-
poj 2299 Ultra-QuickSort :归并排序求逆序数
点击打开链接 Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 34676 Accepted ...
-
poj 2299 Ultra-QuickSort 归并排序求逆序数对
题目链接: http://poj.org/problem?id=2299 题目描述: 给一个有n(n<=500000)个数的杂乱序列,问:如果用冒泡排序,把这n个数排成升序,需要交换几次? 解题 ...
-
[CF 351B]Jeff and Furik[归并排序求逆序数]
题意: 两人游戏, J先走. 给出一个1~n的排列, J选择一对相邻数[题意!!~囧], 交换. F接着走, 扔一硬币, 若正面朝上, 随机选择一对降序排列的相邻数, 交换. 若反面朝上, 随机选择一 ...
-
POJ2299 Ultra-QuickSort(归并排序求逆序数)
归并排序求逆序数 Time Limit:7000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Descri ...
-
HDU 3743 Frosh Week(归并排序求逆序数)
归并排序求逆序数 #include <iostream> #include <cstdio> using namespace std; #define maxn 1000005 ...
-
hiho一下 第三十九周 归并排序求逆序数
题目链接:http://hihocoder.com/contest/hiho39/problem/1 ,归并排序求逆序数. 其实这道题也是可以用树状数组来做的,不过数据都比较大,所以要离散化预处理一下 ...
-
题解报告:poj 2299 Ultra-QuickSort(BIT求逆序数)
Description In this problem, you have to analyze a particular sorting algorithm. The algorithm proce ...
-
poj 2299 Ultra-QuickSort (归并排序 求逆序数)
题目:http://poj.org/problem?id=2299 这个题目实际就是求逆序数,注意 long long 上白书上的模板 #include <iostream> #inclu ...
-
poj2299解题报告(归并排序求逆序数)
POJ 2299,题目链接http://poj.org/problem?id=2299 题意: 给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列. 思路: 其实就 ...
随机推荐
-
ASP.NET Core应用的错误处理[2]:DeveloperExceptionPageMiddleware中间件如何呈现&ldquo;开发者异常页面&rdquo;
在<ASP.NET Core应用的错误处理[1]:三种呈现错误页面的方式>中,我们通过几个简单的实例演示了如何呈现一个错误页面,这些错误页面的呈现分别由三个对应的中间件来完成,接下来我们将 ...
-
C#进阶系列——DDD领域驱动设计初探(四):WCF搭建
前言:前面三篇分享了下DDD里面的两个主要特性:聚合和仓储.领域层的搭建基本完成,当然还涉及到领域事件和领域服务的部分,后面再项目搭建的过程中慢慢引入,博主的思路是先将整个架构走通,然后一步一步来添加 ...
-
LRU implement Data Structure analysis
三种数据结构实现的LRU对比分析: 自适应循环链表, 跳表 和 伸展树 对比发现 : 跳表比其他两个会好一些(命中率) 来自论文 Performance Analysis of LRU
-
echarts .NET类库开源
前言: 2012年从长沙跑到深圳,2016年又从深圳回到长沙,兜兜转转一圈,又回到了原点.4年在深圳就呆了一家公司,回长沙也是因为深圳公司无力为继,长沙股东老板挽留,想想自己年纪也不小了.就回来了,在 ...
-
Linux中vi编辑器的用法
实验一: vi编辑器的模式切换 1. 实验目标:熟练掌握vi编辑器的三种模式间切换及其特点 2. 实验操作步骤: 步骤一: 进入vi编辑器即命令模式 进入vi编辑器可以在命令终 ...
-
extjs 中动态给gridpanel 复选框赋值
最近在搞extjs时需要动态根据数据给gridpanel的复选框赋值 网上看了很多 ,多不行,最后找到一个好使的方法 如下: RBACformPanel.getSelectionModel().sel ...
-
【Xamarin挖墙脚系列:配置Mac之间的连接问题】
原文:[Xamarin挖墙脚系列:配置Mac之间的连接问题] 首先建议把MAC的防火墙关掉,呵呵, 其次,去设置里,允许所有用户远程登录连接MAC
-
bootstrap模态框垂直居中
很久没有写东西了,之前想写一些移动端的东西以后补上吧,移动端发展还是蛮快的,回正题. 因为最近在弄一个系统,系统中引用了bootstrap,发现模态框垂直不居中,遂搜索了一下,也都试了一下,无非都是在 ...
-
Hashtable、ConcurrentHashMap源码分析
Hashtable.ConcurrentHashMap源码分析 为什么把这两个数据结构对比分析呢,相信大家都明白.首先二者都是线程安全的,但是二者保证线程安全的方式却是不同的.废话不多说了,从源码的角 ...
-
我的2018:OCR、实习和秋招
真的是光阴似箭,好像昨天还沉浸在考研成功的喜悦,今天却要即将步入2019年,即将硕士毕业.老规矩,还是在每一年的最后一天总结今年以及展望明年.回首2018,经历的东西特别多,视野也开阔了不少,可以说, ...