1、音樂水柵解題中山紀念中學 高二（19）題目（）Musical Water-fence一天，在洗衣服的時候突發奇想，發明了一種音樂水柵。音樂水柵是這樣子的：它的下部是 N 個長方體的音樂木塊并列組成的。每個木塊的長度都是 1，而寬度可能各不相同。為了沒有重復的音調，使得任意兩塊的高度都不相同。水柵前后被兩塊極大的玻璃夾著。在每一個音樂木塊的上都有一個水龍頭。當把它開啟后，水就會掉下來，與木塊發生非彈性碰撞時發出輕脆、優雅、動聽。下圖為正視圖：（1）當水流滴到一個沒有水的木塊上，就會分成相同的兩部分往左右兩個方向流去。比如在上圖的第三塊木塊放水：水由于重力都流到第二塊和第四塊上。（2）當水滴到水上

2、，就會與水融為一體。譬如當水滴到第二塊上，水積累到一定程度后，就會流到第四塊木塊上。現在編寫了一個音樂譜。該譜按時間前后順序分成一個一個的 M 個命令，每一個命令都是“在第 Wi 個木塊上注入體積為 Vi 的水”。但是是一個不愛浪費的人，所有他想知道這音樂譜左邊和右邊各浪費了多少水。有必要的話，他要改譜哦。輸入文件：第一行兩個數 N，M。接下來 N 行，每行兩個實數，分別表示寬度和高度。再接下來 M 行，每行兩個實數，表示 Wi、Vi。輸出文件：第一行輸出通過左邊流出浪費的水的體積。第二行輸出通過右邊流出浪費的水的體積。保留 3 位小數。輸入樣例：6 245 73 6輸出樣例：0.5003.5

3、00數據范圍：50%的數據中 N、M100。70%的數據中 N、M1000。80%的數據中 N、M10000。90%的數據中 N、M100000。100%的數據中 N、M1000000。初步分析很多同學看完這個題以后就立即想到模擬算法，并很快想到用一些高級數據結構去優化算法。但是這個方法相當麻煩。為了說明模擬算法的復雜性，我簡單地說說用并查集來模擬的算法。一開始，當水滴到一個木塊上之后，它就分成兩條水流各奔東西。考慮向左邊流的水流 Water1。從初始的木塊開始向左找到第一塊木塊 Left，使得 Left 左邊的木塊比它高。如果找到的話，情況（1）Left 右邊的木塊比 Left 矮（這時 L

4、eft 會等于初始木塊）。那么就水流的方向改為向右；情況（2）Left 右邊的木塊比 Left 高。那么 Water1 就會有一部分在 Left，如果 Left 的蓄水量大于 Water1，那么就把 Left 的高度增大為 Water1/WideLeft，否則，就把它的高度設為兩邊木塊較矮的那塊的高度，并合并高度相同的那兩塊木塊、把Water1 減少 Left 的蓄水量并且把 Water1 置于初始的木塊地重復上述的步驟；如果找不到，那么這水就會從左邊流出去。對于向左邊流的水流，分析與上述相似。如果地做的話，時間復雜度就是 O（N*N）。而這里涉及到三個操作合并、找 Left 和 Right。

5、這時可以用三類并查集來完成這些任務，時間復雜度為 O（N*(N)）。解放、聯系實際、深入分析根據生活實踐的認識，水的流放順序是不影響結果的。這樣可以假設水是以任意順序掉下來的，甚至同時掉下。然后，不妨發揮一下想象，如果水量是無限地多，情況會怎么樣呢？憑借經驗，我們描繪出下圖：現在來深入分析一下。首先分析水從最左邊流出的情況：如果 P1 右邊的某些水能夠從最左邊流出,那么 P1 到P2 之間的凹溝一定是裝滿水的。如果 P2 右邊的某些水能夠從最左邊流出，那么 P1 到 P2 之間、P2 到 P3 之間的凹溝一定是裝滿水的。類似地，如果 Pi 右邊的某些水能夠從最左邊流出，那么 P1 到 P2 之

6、間、P2到 P3 之間Pi 到 Pi+1 之間的凹溝一定都滿的。有了以上結論之后，對于最終狀態中的 Pi，假如 Pi 使得 P1 到 P2 之間、P2 到 P3 之間Pi-1 到 Pi 之間的凹溝都滿了并且 Pi 到 Pi+1 之間的凹溝不是滿的或不存在，那么答案就是 F(Pi)=P1 到 Pi-1 的降水量Pi 的降水量2P1 到 Pi 的蓄水量。Pi 的降水量之所以除以 2 是因為有一半的水往右流走了。如果上述的假設不成立，F(i)不會大于。分兩種情況考慮：（1）如果 P1 到P2 之間、P2 到 P3 之間Pi-1 到 Pi 之間的凹溝都滿了，但Pi 到Pi+1 之間的凹溝還是滿的，這時

7、就等價于砍去Pi 后面的降水量，顯然這時求出的 F(Pi)值不會大于；圖釋：P1 是最左邊的木塊，P2 是 P1 右邊第一個比P1 高的木塊，P3 是P2 右邊第一個比P2 高的木塊Q1 是最右邊的木塊，Q2 是 Q1 左邊第一個比 Q1 高的木塊.（ ）如果 6 到 6 之間、6 到 6 之間6O 到 6O 之間的凹溝不是都滿的，這時流出的是6 到 6O 的降水量6O 的降水量 6 到 6O 的一部分蓄水量$6 到 6O 的降水量6O 的降水量 6 到 6O 的蓄水量#, 6O 。之所以是有“一部分”，是因為 6 到 6 之間、6 到 6 之間6O 到 6O 之間有凹溝不是滿的。綜上所述，,

8、 6O 值是不會超過的并且有一個是，所以就是。對于水從最右邊流出來的情況，分析與上述相似。具體實現時可以把整個圖翻轉，調用同樣的函數求兩個結果。這種解法形象、合理、簡單、高效。時間復雜度：系數小的 5（4）。編程復雜度：低。總結認識的根本來源是實踐。在學習作為具體科學的信息學時，應該要做到不唯書、不唯上、只唯實，在生活實踐不斷地獲取經驗、認識，并用這些經驗、認識去解決問題（回歸實踐）。從長遠來看，信息學的前進也只能依靠的不斷實踐。這題目的產生、解決可以說是新穎的，因為這道題目是源于洗衣生活，同時我也利用生活經驗來解決。我希望在信息學競賽中能有這種類型的題目。代碼program CQF_MWF;

9、var h,l,v:array1.1000000 of extended; n,m:long ;procedure init; var i,j,k:long ; beginreadln(n,m); for i:=1 to n doreadln(li,hi); fillchar(v,sizeof(v),0); for i:=1 to m do beginreadln(j,k); vj:=vj+k;end; end;procedure work; var i:long;procedure swap(var a,b:extended); var tmp:extended;begintmp:=a; a

10、:=b; b:=tmp;end; procedure cal; var i:long;la,s,ans,hw:extended; beginans:=0; la:=0;hw:=0;s:=0;for i:=1 to n do beginif hila then beginif hw-s+vi*0.5ans then ans:=hw-s+vi*0.5;la:=hi; end;hw:=hw+hi*li+vi; s:=s+la*li;end;wrin(ans:0:3);end; begincal;for i:=1 to n div 2 do begin swap(hi,hn+1-i);swap(li,ln+1-