Poj 2299 - Ultra-QuickSort 离散化,树状数组,逆序对
2024-10-21 10:27:09
Ultra-QuickSort
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. 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 Sample Output 6 Source 题意:给定n个数,只能交换相邻的两个元素,至少交换几次,成为递增序列。
题解:
明显要求序列的逆序对数目。。。
对于样例:
5
9 1 0 5 4
我们将其排序:
0 1 4 5 9
在每个位置上初始放为1.
1 1 1 1 1
然后,从原序列开始遍历。
先到9,我们把其排好序的位置拿出,即为5。
然后统计位置5之前有多少1。
1 1 1 1 1
———— > 4个 ans+=4
然后把5号位置放为0。
1 1 1 1 0
继续操作即可。。。
这个树状数组维护即可。。。
注意开long long和原序列排序后要去重。。。
#include<bits/stdc++.h> |
最新文章
- 【转】PowerShell入门(十二):编写PowerShell管理单元和二进制模块
- 利用SoapUI 测试web service的方法介绍
- 我的c++学习(7)引用和复制构造函数
- 使用redis的五个注意事项
- hibernate多表查询,结果封装在自己定义的一个实体类当中(在自己定义的类中增加构造函数)
- word 使用宏批量设置表格
- Knockout.js, Asp.Net MVC and Bootstrap 前端设计
- 概述什么是OSGi框架
- Tkinter教程之Text(2)篇
- hdu 1195 广度搜索
- hdoj 5443 The Water Problem【线段树求区间最大值】
- Browsing History
- API 之 MessageBox
- linux系统文件属性-硬连接、软连接
- redis client protocol 分解
- Linux下jdk环境配置
- 最基础的 swift 语言
- DLC 基本定律与规则2
- Codefoces 277 E. Binary Tree on Plane
- REST easy with kbmMW #24 使用kbmMW实现JSON/XML/YAML转换成对象