- 浏览: 601186 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ2299题意:
给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力,会超时。
样例:(2次测试)
Sample Input
5 序列中数的个数
9
1
0
5
4
3 序列中数的个数
1
2
3
0 n=0结束
Sample Output
6
0
其中需排序的数的范围0---999 999 999;显然数组不能开这么大,序列中数的个数N不大于500000,故先要将给出的序列离散到[1,500000]。
例: int a[] = {10000000, 10, 2000, 20, 300};
那么离散化后a[] = {5, 1, 4, 2, 3},是一个一一对应关系,而且满足原来的大小关系,离散的方法如下:
POJ2299解题思路: 其实这题就是求这个序列的逆序数,离散化后用线段树边查询边插入即可。
下面是AC过的代码:(请参考:http://128kj.iteye.com/blog/1741183
源码:
我怎么觉得只要两次就可以了
91054 第一次交换9和0,得到01954
01954 第二次交换9和4,得到01459
我怎么感觉是交换两次就行了。9和0和4.
给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力,会超时。
样例:(2次测试)
Sample Input
5 序列中数的个数
9
1
0
5
4
3 序列中数的个数
1
2
3
0 n=0结束
Sample Output
6
0
其中需排序的数的范围0---999 999 999;显然数组不能开这么大,序列中数的个数N不大于500000,故先要将给出的序列离散到[1,500000]。
例: int a[] = {10000000, 10, 2000, 20, 300};
那么离散化后a[] = {5, 1, 4, 2, 3},是一个一一对应关系,而且满足原来的大小关系,离散的方法如下:
(1)定义一个类,用来表示序列中的一个数。 class Node implements Comparable{ int val;//值 int no;//序号 public int compareTo(Object o) { return this.val - ((Node) o).val; } } (2)然后将所给序列用下面数组p表示,排序p并离散化. int data[] = new int[n]; Node[] p=new Node[n]; for (int i = 0; i < n; i++) { p[i]=new Node(); p[i].val=in.nextInt(); p[i].no=i; } Arrays.sort(p); for(int i=0;i<n;i++){ data[p[i].no]=i+1; }//以上是使其离散化
POJ2299解题思路: 其实这题就是求这个序列的逆序数,离散化后用线段树边查询边插入即可。
下面是AC过的代码:(请参考:http://128kj.iteye.com/blog/1741183
import java.util.Scanner; import java.util.Arrays; import java.util.Comparator; import java.io.BufferedInputStream; class Seg_Tree {//线段树节点 int left,right; int val;//区间内已插入的节点数 int calmid() { return (left+right)/2; } } class Node implements Comparable{ int val; int no; public int compareTo(Object o) { return this.val - ((Node) o).val; } } public class Main{ private int LL(int x) { return x<<1;} //两倍; private int RR(int x) { return x<<1|1;} //两倍+1; Seg_Tree tt[]; public Main(){ tt=new Seg_Tree[ 1048578];//用数组实现线段树 for(int i=0;i< 1048578;i++) tt[i]=new Seg_Tree(); } private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树 tt[idx].left = left; tt[idx].right = right; tt[idx].val = 0; if(left == right) return ; int mid = tt[idx].calmid(); build(left,mid,LL(idx)); build(mid+1,right,RR(idx)); } private void insert(int aim,int l,int r,int k){ //将aim插入到线段树 if(tt[k].left==aim&&tt[k].right==aim) { tt[k].val++;return ; } if(aim<=tt[k].calmid()) insert(aim,l,tt[k].calmid(),LL(k)); else insert(aim,tt[k].calmid()+1,r,2*k+1); tt[k].val=tt[LL(k)].val+tt[RR(k)].val; } //查询[left,right]中已插入的节点数 private int query(int left,int right,int idx){ if(left == tt[idx].left && right == tt[idx].right) return tt[idx].val; int mid = tt[idx].calmid(); if(right <= mid){ return query(left,right,LL(idx)); } else if(mid < left) { return query(left,right,RR(idx)); } else { return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx)); } } public static void main(String[] args){ Scanner in = new Scanner(new BufferedInputStream(System.in)); while (in.hasNext()) { int n = in.nextInt(); if (n == 0) { break; } int data[] = new int[n]; Node[] p=new Node[n]; for (int i = 0; i < n; i++) { p[i]=new Node(); p[i].val=in.nextInt(); p[i].no=i; } Arrays.sort(p); for(int i=0;i<n;i++){ data[p[i].no]=i+1; }//以上是使其离散化 Main ma=new Main(); ma.build(1,n,1); long sum = 0; for(int i=0;i<n;i++){ sum += ma.query(data[i],n,1);//先查询 ma.insert(data[i],1,n,1);//后插入 } System.out.println(sum); } } }
源码:
- Main2299.rar (1.2 KB)
- 下载次数: 3
评论
3 楼
128kj
2012-12-06
不好意思,没写清题目意思,已改过来了。
给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。
给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。
2 楼
mfkvfn
2012-12-06
引用
例如将"91054"变成"01459",最小交换6次
我怎么觉得只要两次就可以了
91054 第一次交换9和0,得到01954
01954 第二次交换9和4,得到01459
1 楼
HalfSmoked
2012-12-06
引用
例如将"91054"变成"01459",最小交换6次
我怎么感觉是交换两次就行了。9和0和4.
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3744题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1654POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2394北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1986import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3053POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1478POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1928题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1639关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1869关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1877POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1894POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1764POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1643分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2248接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1543关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1396接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2467当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1822关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1815关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1817关于树状数组,请参考:http://128kj.iteye.c ...
相关推荐
在这个场景中,我们使用线段树来求解逆序数,可以实现O(n log n)的时间复杂度,其中n是数组的长度。线段树通过将数组分割成一系列连续的子区间,并为每个子区间维护一些信息,可以快速地查询或修改这些区间的信息。 ...
### 归并排序求逆序数 #### 一、引言 在计算机科学与数据结构领域,排序算法是基础且重要的组成部分。其中,归并排序作为一种高效稳定的排序方法,在实际应用中有着广泛的应用场景。本篇文章将围绕如何利用归并...
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
POJ 2299 是一个经典的逆序数对算法题目,它要求计算一个序列中的逆序数对数量。该问题可以使用多种算法解决,包括暴力枚举、归并排序、树状数组等。 暴力枚举算法 暴力枚举算法是最简单的解决方法,它通过枚举...
在`POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】.cpp`文件中,你应该能够找到使用归并排序算法计算逆序对的实现。这种方法相比于直接求解,虽然增加了额外的排序操作,但大大提高了时间效率,尤其在处理大...
算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅
利用归并排序求逆序数,复杂度在O(nlgn)含测试用例
《算法-求排列的逆序数(信息学奥赛一本通-T1237)》这个主题涉及到的是计算机科学中的一个重要概念,逆序对或逆序数,它在算法设计和分析中扮演着关键角色,特别是在解决排序和组合优化问题时。逆序数是衡量一个...
求逆序数 求逆序数 求逆序数 求逆序数 求逆序数
在计算机科学和编程领域,"数组的逆序数"是一个重要的概念,特别是在算法分析和排序算法中。逆序数(Inversion Count)是指在数组或序列中,如果一个大于其后面的元素,则这样的对称为逆序对。逆序数就是数组中逆序...
- **解决思路**: 使用线段树来维护区间内的逆序对数量,通过动态规划的方法来求解最小逆序数。 - **关键步骤**: - 定义线段树节点存储区间内的逆序对数量。 - 构建线段树,维护区间内的逆序对数量。 - 对于每次...
在这里要用到__int64,也就是long long int
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
### 归并求逆序对 C语言实现 #### 知识点详解 1. **归并排序算法**:归并排序是一种经典的排序算法,采用分治策略来对数组进行排序。其基本思想是将待排序的数据分成两部分,分别对这两部分数据进行排序,然后再...
学习电脑信息用while循环获得逆序数 在计算机编程中,while循环是一种常用的循环结构,可以用来实现各种复杂的算法。今天,我们将学习如何使用while循环来获得逆序数。 什么是逆序数?逆序数是指将一个数字的各个...
- **POJ 1151**:结合了线段树和离散化的技巧来求解矩形面积的并集。这需要对输入的坐标进行离散化处理,以减少空间复杂度,并使用线段树维护区间信息。 - **POJ 1177**:求解矩形周长的并集。此题与POJ 1151类似,...
这意味着,如果我们对同一序列进行多次操作,可以利用这一特性来优化算法,例如通过持久化线段树来避免重复计算。 线段树的合并操作是其独特之处,它可以用来高效地处理一系列合并操作,如在POI18 rot题目中,解决...
- 在合并两个大小分别为m和n的已排序子数组时,遍历每个元素,统计小于当前元素的元素个数,这个数量就是逆序对。 - 归并排序的总时间复杂度为O(n log n),其中n是数组的长度。 2. **树状数组(斐波那契堆)**: ...
- Atlantis(1151):经典的扫描线求矩形面积交,通过离散化和线段树实现。 - Picture(1177):要求求解矩形周长的并,需要维护线段树中的多个信息。 - K-th Number(2155):使用线段树维护归并排序树,并采用...
求逆序数的C语言实现.docx