栈队列堆试题解析.pptVIP

Juice参考程序Pascal版 juice procedure init; //初始化把四周的“边”放入堆中 var i,j :integer; begin for i:=1 to yy do begin //左右两边 add(i,1,d[i,1]); add(i,xx,d[i,xx]); end; for j:=2 to xx-1 do begin //上下两行 add(1,j,d[1,j]); add(yy,j,d[yy,j]); end; for i:=2 to yy-1 do //内部标记为还没有处理 for j:=2 to xx-1 do v[i,j]:=true; end; Juice参考程序Pascal版 juice procedure work; //主要处理过程 var nh,nx,ny,i :longint; begin while (counter0) do begin nh:=heap[1].h; //取“边上”最小高度元素 for i:=1 to 4 do begin //看它四周 nx:=heap[1].x+dx[i]; ny:=heap[1].y+dy[i]; if v[nx,ny]=false then continue; //是否处理过 if nhd[nx,ny] then begin //比“边”低，则盛水 ans:=ans+nh-d[nx,ny]; d[nx,ny]:=nh; //改成边 end; add(nx,ny,d[nx,ny]); v[nx,ny]:=false; //加“边”入堆 end; swap(heap[1],heap[counter]); dec(counter); down(1); //删除 end; end; Juice参考程序Pascal版 juice Begin //主过程 assign(input,juice.in); reset(input); assign(output,juice.out); rewrite(output); readln(xx,yy); for i:=1 to yy do for j:=1 to xx do read(d[i][j]); init; work; writeln(ans); close(input); close(output); end. 1、Tallest试题有修正 updata your family site your site here LOGO c LOGO 2010.4.8试题解析 江涛 队列、栈、堆 cover 目录 Mooo---单调队列( 栈) tallest---括号匹配”栈” Juice---堆 3 Cover---队列 1 2 4 目录 cover 【试题描述】 ?有 N 个时间段，某个时间段可能包含其它时间段。 ? 请找出能包含其它时间段最多的那个段，并计算出它包括的其它时间段有多少？ 【数据范围】 ?1 = N = 25,000 ?1 =?时间段开始和结束点 = 2,000,000,000 任意两个时间段的端点不相同 cover 【样例】 输入 41 72 35 64 10??? ???? 输出? 2 ? 第1段包含2,3两段??? ? *-----------*????? |?????????? |*-----------*|?????????? || *-*?? *-* || | |?? | | |1 2 3 4 5 6 7 8 9 10 cover分析 cover O(N^2)超时，因此，我们不能简单枚举。 只要O(NlogN)时间复杂度即可，自然想到先排序。但是对段排序，还是对端点排序？这个要想清楚。我们先看看对时间点自然扫描。 与括号匹配类似，左端点简单进入，右端点来时我们分情况讨论： cover分析 cover (A) 如果当前点 ti 是右端点，且与“当前第1”个时间点“匹配”---即是一个时间段的两端点: