- 浏览: 583912 次
- 来自: ...
文章分类
最新评论
-
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 3660题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1527POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2327北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1945import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2981POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1848题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1830POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1563分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1354接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2418当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1766关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1674关于树状数组,参看:http://128kj.iteye.co ... -
初步了解树状数组
2012-12-07 14:18 1701一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1749213
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1754170
NULL 博文链接:https://128kj.iteye.com/blog/1753387
NULL 博文链接:https://128kj.iteye.com/blog/1746750
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1772172
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1752661
NULL 博文链接:https://128kj.iteye.com/blog/1759266
NULL 博文链接:https://128kj.iteye.com/blog/1750462
POJ 1328 java做!雷达问题!java版本!AC答案~
用java的biginteger实现的poj1001,比较简单的方法
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1733777