首页 > 代码库 > 花神倒果汁
花神倒果汁
花神倒果汁
(juice.pas/c/cpp)
【题目描述】
为了庆祝花神开花，花神决定举办一个宴会。其中有一个游戏叫倒果汁。
果汁容器的底座是一个独立的N×M的矩阵，矩阵的每个格点有一个高度，表示这个格子正上方有多少个1×1×1的方块。相邻两个方块被粘得严实，不会漏。
现在花神给你一盒果汁，问你在不使果汁满出来的情况下，容器最多能装下多少立方单位的果汁。
【输入格式】
第一行两个整数N和M。
接下来M行，每行N个整数，表示这个格子的高度H[i][j]。
【输出格式】
仅一行，表示答案。
【样例输入】
4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9
【样例输出】
12
【样例解释】
矩阵变成了：
5 8 7 7
5 5 5 5
7 5 7 1
8 9 7 9
9 8 9 9
3+4+4+1=12
【数据规模】
对于100%的数据：1≤M,N≤300；H[i][j]≤10^9；
这题就是著名的“短板效应”——一个木桶里的水最多能装多少取决于其最短的一条版高度是多少。那么，我们自然可以把外面四周边界看作木桶的“板”。我们要想在里面装水，我们自然要知道这最短的一根版。但因为题目中说“相邻两个方块被粘得严实，不会漏”，那么最角落的4个点是根本不需要的，直接打上vis[i][j]=true就是了。除此之外，边界上的点也要打上true，并且要找个最低的板。那么需要多次找最低的板，我们自然想到了用堆来刷。最低的板找到了，在呢？例如下图：
-------------
| | | | |
-------------
| | | |/ \|
-------------
| | |<-|Ls|
-------------
| | | |\ /|
-------------
| | | | |
-------------
假设Ls是最低的板，那么他可以向4个方向扩展（这里只有3个）。那么，我们每扩展到一个格子xx，yy，如果他是合法且没有被更新过，那么才能去更新它，因为每个点最多只会被更新1次（因为我们每次都是寻找这些板的最矮的地方，从这个当前最矮的地方扩展到xx，yy。由于我们只是考虑板，而暂时不考虑木桶的内部，所以导致里面的点也就是后入堆的点影响不到外面的点也就是先入堆的点，那么我们从堆里面get出来的x，y这个点是当前木桶的最短一块木板（所以木桶是有可能变成不规则的），当他更新了点xx，yy以后，接下去的任何一点去更新xx，yy都不是最优的，所以我们只会让每个点入堆一次，也就是说他只会被更新一次，并且它也只能更新其他格子一次）。那么，每当这个格子合法且未更新过，那么要把他打上vis=true，而且要更新new[xx][yy]——
1.if old[xx][yy]<new[x][y] then begin inc(ans,new[x][y]-old[xx][yy]); new[xx][yy]
:=new[x][y];
2.else new[xx][yy]:=old[xx][yy];
对于情况1，就是说如果xx，yy的木板高度<x，y已经更新过（可能有水）的总高度，那么此时，xx，yy是可以达到new[x][y]的高度的，于是ans+=改变的值；
对于情况2，就是说如果xx，yy的木板高度>=x，y已经更新过（可能有水）的总高度，那么此时，xx，yy是无论如何不能倒水下去的，所以new的高度等于old的高度的。
那么，更新过后，我们还要将它put入堆去更新其他的格子。
那么最后知道len=0也就是所有点都更新过了的时候就break掉，输出就好了。
1 const fl:array[0..3,0..1] of longint=((-1,0),(0,1),(1,0),(0,-1)); 2 maxn=305*305; 3 var map,dis:array[0..305,0..305] of longint; 4 vis:array[0..305,0..305] of boolean; 5 heap:array[0..maxn] of record 6 x,y,h:longint; 7 end; 8 n,m,ans,len:longint; 9 procedure init; 10 var i,j:longint; 11 begin 12 readln(m,n); 13 for i:=1 to n do 14 for j:=1 to m do read(map[i][j]); 15 end; 16 procedure put(x,y,h:longint); 17 var son:longint; 18 begin 19 inc(len); heap[len].h:=h; heap[len].x:=x; heap[len].y:=y; son:=len; 20 while son>1 do 21 begin 22 if heap[son>>1].h>heap[son].h then begin 23 heap[maxn]:=heap[son]; 24 heap[son]:=heap[son>>1]; 25 heap[son>>1]:=heap[maxn]; 26 end 27 else break; 28 son:=son>>1; 29 end; 30 end; 31 procedure get; 32 var fa,son:longint; 33 begin 34 heap[1]:=heap[len]; dec(len); fa:=1; 35 while fa<<1<=len do 36 begin 37 if (heap[fa<<1].h<heap[fa<<1+1].h) or (fa<<1+1>len) then son:=fa<<1 38 else son:=fa<<1+1; 39 if heap[fa].h>heap[son].h then begin 40 heap[maxn]:=heap[son]; 41 heap[son]:=heap[fa]; 42 heap[fa]:=heap[maxn]; 43 end 44 else break; 45 fa:=son; 46 end; 47 end; 48 procedure main; 49 var i,x,y,xx,yy:longint; 50 begin 51 for i:=2 to m-1 do begin dis[1][i]:=map[1][i]; put(1,i,map[1][i]); vis[1][i]:=true; end; 52 for i:=2 to m-1 do begin dis[n][i]:=map[n][i]; put(n,i,map[n][i]); vis[n][i]:=true; end; 53 for i:=2 to n-1 do begin dis[i][1]:=map[i][1]; put(i,1,map[i][1]); vis[i][1]:=true; end; 54 for i:=2 to n-1 do begin dis[i][m]:=map[i][m]; put(i,m,map[i][m]); vis[i][m]:=true; end; 55 vis[1][1]:=true; vis[1][m]:=true; vis[n][1]:=true; vis[n][m]:=true; 56 while len>0 do 57 begin 58 x:=heap[1].x; y:=heap[1].y; get; 59 for i:=0 to 3 do 60 begin 61 xx:=x+fl[i][0]; yy:=y+fl[i][1]; 62 if (xx<1) or (xx>n) or (yy<1) or (yy>m) then continue; 63 if vis[xx][yy] then continue; 64 vis[xx][yy]:=true; 65 if dis[x][y]>map[xx][yy] then begin inc(ans,dis[x][y]-map[xx][yy]); dis[xx][yy]:=dis[x][y]; end 66 else dis[xx][yy]:=map[xx][yy]; 67 put(xx,yy,map[xx][yy]); 68 end; 69 end; 70 end; 71 procedure print; 72 begin 73 writeln(ans); 74 end; 75 begin 76 init; 77 main; 78 print; 79 end.
花神倒果汁