- 浏览: 604401 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
关于树状数组,请参考:http://128kj.iteye.com/blog/1743633
POJ 2481题意:
有n头牛(编号为1~n),每一头牛都有一个吃草区间[S, E],如果对于牛i和牛j来说,它们的吃草区间满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的吃草区间,要求输出每头牛有几头牛比其强壮。
其中:1 <= N <= 100000, 0 <= S < E <= 100000
样例:
Sample Input
3 (3头牛)
1 2 牛的[s,e]值
0 3
3 4
0
Sample Output
1 0 0 (比第一头牛强的有一头,比第二头牛强的没有,比第三头牛强的没有)
分析:
建一个全0的树状数组,然后将牛一个一个插入树状数组,当然必须先对e按照降序排列,每加入一只牛,当前已经加入树状数组的牛的s如果比这只牛小,那么那些牛就更强壮,所以这是在树状数组里的求和问题,只要求出在插入s之前已插入了多少头牛(求和)。另外,由于排序后,顺序和开始给出数据时的顺序不同,所以需要记录一下开始给出数据时的顺序。
下面是AC过的代码:
POJ 2481题意:
有n头牛(编号为1~n),每一头牛都有一个吃草区间[S, E],如果对于牛i和牛j来说,它们的吃草区间满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的吃草区间,要求输出每头牛有几头牛比其强壮。
其中:1 <= N <= 100000, 0 <= S < E <= 100000
样例:
Sample Input
3 (3头牛)
1 2 牛的[s,e]值
0 3
3 4
0
Sample Output
1 0 0 (比第一头牛强的有一头,比第二头牛强的没有,比第三头牛强的没有)
分析:
建一个全0的树状数组,然后将牛一个一个插入树状数组,当然必须先对e按照降序排列,每加入一只牛,当前已经加入树状数组的牛的s如果比这只牛小,那么那些牛就更强壮,所以这是在树状数组里的求和问题,只要求出在插入s之前已插入了多少头牛(求和)。另外,由于排序后,顺序和开始给出数据时的顺序不同,所以需要记录一下开始给出数据时的顺序。
下面是AC过的代码:
import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStreamWriter; import java.io.IOException; import java.util.Arrays; class TNode implements Comparable{//表示一头牛 int s;//牛吃草的左端点 int e;//右端点 int label;//牛的序号 public int compareTo(Object o) { int v=((TNode)o).e; if(this.e!=v) //按右端点降序排列 return v-this.e; return this.s-((TNode)o).s;//右端点相等,按左端点升序排序 } public String toString(){ return ("["+s+","+e+"]"); } } public class Main{// static int N=100015; TNode[] cow; int cal[];//树状数组 int res[];//res[i]表示比牛i强壮的牛的个数 int maxn;//右端点的最大值 public Main(){ } private int lowbit(int t){//计算cal[t]展开的项数 return t&(-t); } private int Sum(int k){ //求前k项的和. int sum=0; while(k>0){ sum+=cal[k]; k=k-lowbit(k); } return sum; } private void update(int i,int x){ //增加某个元素的大小,给某个节点 i 加上 x while(i<=maxn){ cal[i]=cal[i]+x; //更新父节点 i=i+lowbit(i); } } public static void main(String args[]) throws IOException{ Main ma=new Main(); ma.go(); } public void go() throws IOException{ StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while(true) { st.nextToken(); int n= (int) st.nval; //牛的个数 if(n==0) break; cow=new TNode[N]; cal=new int[N]; res=new int[N]; for(int i=0;i<N;i++){ cow[i]=new TNode(); // cal[i]=0; } for(int i=0;i<n;i++) {//读入牛的吃草区间 st.nextToken(); cow[i].s=(int) st.nval; st.nextToken(); cow[i].e=(int) st.nval; cow[i].s++; cow[i].e++; cow[i].label=i;//牛的原始序号 if(cow[i].e>maxn) maxn=cow[i].e;//最大右端点 } Arrays.sort(cow);//排序 // for(int i=0;i<n;i++) // System.out.println(cow[i]); for(int i=0;i<n;i++) { if(i!=0&&cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e)//两头牛有相同的吃草区间 res[cow[i].label]=res[cow[i-1].label];//它们有相同的答案 else res[cow[i].label]=Sum(cow[i].s);//统计比cow[i].label这头牛强的牛的数目 update(cow[i].s,1);//更新 } System.out.printf("%d",res[0]); for(int i=1;i<n;i++) System.out.printf(" %d",res[i]); System.out.println(); } } }
- 11089337_AC_8657MS_26592K.zip (1.3 KB)
- 下载次数: 0
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3776题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1681POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2404北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1989import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1486POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1936题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1647关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1876关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1897POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1915POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1771POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1664分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2268接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1551关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2472当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1846关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1846关于树状数组,参看:http://128kj.iteye.co ... -
初步了解树状数组
2012-12-07 14:18 1791一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...
标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...
它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
标题“堆排序练习:POJ 2388”指的是一个关于使用堆排序算法解决编程竞赛问题的实践案例。在编程竞赛中,如POJ(Programming Online Judge)平台上的问题2388,参赛者经常需要高效地解决排序问题,而堆排序作为一种...
标题 "大(小)顶堆练习:POJ 1442" 提示我们这是一个关于数据结构和算法的练习题目,特别关注大顶堆或小顶堆的应用。在计算机科学中,大顶堆和小顶堆是两种特殊的二叉堆,它们分别保证了根节点是其子树中最大或最小...
这个练习题目,"POJ 2388",显然是通过编程实现直接插入排序来解决一个特定的问题。在这个问题中,我们需要理解直接插入排序的机制,并能用Java语言编写出高效的代码。 直接插入排序的基本步骤如下: 1. 从第二个...
* 最小树形图:POJ3164 * 次小生成树 * 无向图、有向图的最小环 三、数据结构 * RMQ:POJ3264、POJ3368 * 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最...
"C++ 数组扩充"提示我们问题可能与如何在C++编程语言中处理数组的增长有关,而"poj 26_poj 2682_poj26"似乎是重复提及问题编号,可能是用户在整理文件时的习惯。 描述中提到的“数链思想”可能是指一种处理数组元素...
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
2. **树形结构** - 示例题目:poj2388, poj2299 3. **字典树(Trie)** - 字典树是一种高效的数据结构,用于存储大量字符串。 - 示例题目:poj2513 4. **哈希表** - **散列表的应用**:常用于快速查找、插入和...
在提供的压缩文件“11132845_AC_3422MS_8416K.java”中,我们可以看到这可能是一个Java程序,其中“AC”通常代表“Accepted”,意味着这个解决方案已经被POJ平台接受,即通过了所有测试用例。后面的“3422MS”表示...
### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
《田忌赛马:POJ 2287 贪心解法解析》 在计算机科学领域,算法是解决问题的核心。"田忌赛马"这个题目来源于古代中国的一个著名故事,而在这个故事的基础上,被引入到了编程竞赛的场景中。POJ(Programming Online ...
(4) 哈希表和二分查找等高效查找法:poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503 (5) 哈夫曼树:poj3253 (6) 堆 (7) trie树:poj2513 四、简单搜索 本部分涵盖了简单搜索,包括深度优先搜索、广度优先...