Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 39782 | Accepted: 14340 |
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
题意:
给出数 n (0 ~ 500000)代表有 n 个数,后给出这 n 个数(0 ~ 999999999),求出需要交换的次数使这个序列变为递增序列。
思路:
树状数组 + 离散化。离散化用 排序 + map 会导致 TLE,所以要用 排序 + 去重 + 二分 来离散化,结果应该要为 long long 型的。题目即为求逆序数,运用树状数组即可求出。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll MAX = 500005; ll num[MAX], s_num[MAX]; ll bit[MAX], n; void add(ll i, ll x) { while (i <= n) { bit[i] += x; i += i & -i; } } ll sum(ll i) { ll s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } int main() { while (~scanf("%I64d", &n) && n) { for (ll i = 0; i < n; ++i) { scanf("%I64d", &num[i]); s_num[i] = num[i]; bit[i + 1] = 0; } sort(s_num, s_num + n); ll ans = 0; for (ll i = 0; i < n; ++i) { int in = lower_bound(s_num, s_num + n, num[i]) - s_num; ans += i - sum(in); add(in + 1, 1); } printf("%I64d\n", ans); } return 0; }
相关推荐
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
主要运用合并排序合的过程,在合的过程中,判断左边是否大于右边,如果是的话,就表示有一个你序对,但是合并排序当判断左边大于右边的时候,右边的值会马上被抽出来,所以如果左边还有比右边大的数的话就判断不了了...
pku acm 2299 Ultra-QuickSort代码,合并排序求逆序数,解题报告请访问:http://blog.csdn.net/china8848
CUDA-quicksort 是一种基于 GPU 的快速排序算法实现。 CUDA-quicksort 旨在利用现代 NVIDIA GPU 的计算能力。 “文献中介绍了两种基于 GPU 的快速排序实现:GPU 快速排序,一种计算统一设备架构 (CUDA) 迭代实现,...
runoob-algorithm-QuickSort2Ways.zip
sort-quicksort-asc 快速排序( arr ) 使用从未排序的数字数组生成排序(升序)数组。 例子 // Direct to lib directory var qsort = require ( './../lib' ) ; // Create some data var data = new Array ( 5 ) ...
前端大厂最新面试题-quickSort
QuickSort-QuickSort
快速排序源代码,采用C++编写,经测试未发现BUG,供大家参考
快速排序与随机快速排序,并且解决问题,计数其中重复排序次数与最大最小次数
PHP_基于php实现的快速排序算法_QuickSort
js代码-quickSort
基础算法和数据结构:DSA 可视化算法:视觉算法 C ++面试:Huihut采访 BTree实现:B-Tree C ++对象模型线段树:SegmentTree C ++面试总结(多方面) C#面试总结(基础) 线段树:SegmentTree 算法 种类 QuickSort ...
Quickselect-QuickSort-with-Covid19Data 具有Covid19数据的Quickselect和QuickSort算法
(由于mergesort复制数组等,因此quicksort基本上更好。) 出色的外部对准(有关详细信息,请参见参考1p.114)。 其他 狄克斯特拉法最短路径搜索 霍纳法通常用于在n元中查找值 欧几里得算法找到最大的公约数 参考 ...
JDK7的时候内置 的排序算法已经由经典快排变成了Dual-Pivot排序算法。那么Dual-Pivot到底是何方圣神,能 比我们学过的经典快排还要快呢?
Sort-QuickSort write a simple demo about QuickSort algorithm 简介 快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 分治法的...
该应用程序以quicksort为例,演示如何使用akka解决分布式递归问题。 使用工作队列方法的类位于com.tsykul.forkjoin.distributed.queue包中。 要运行工作程序,请启动...
基本算法,堆排序和快速排序 要求可在pdf中找到