ioi2007的作業(yè)音樂水柵

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

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

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

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

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

6、間、P2到 P3 之間Pi 到 Pi+1 之間的凹溝一定都滿的。有了以上結(jié)論之后，對于最終狀態(tài)中的 Pi，假如 Pi 使得 P1 到 P2 之間、P2 到 P3 之間Pi-1 到 Pi 之間的凹溝都滿了并且 Pi 到 Pi+1 之間的凹溝不是滿的或不存在，那么答案就是 F(Pi)=P1 到 Pi-1 的降水量Pi 的降水量2P1 到 Pi 的蓄水量。Pi 的降水量之所以除以 2 是因為有一半的水往右流走了。如果上述的假設(shè)不成立，F(xiàn)(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 值是不會超過的并且有一個是，所以就是。對于水從最右邊流出來的情況，分析與上述相似。具體實現(xiàn)時可以把整個圖翻轉(zhuǎn)，調(diào)用同樣的函數(shù)求兩個結(jié)果。這種解法形象、合理、簡單、高效。時間復(fù)雜度：系數(shù)小的 5（4）。編程復(fù)雜度：低?？偨Y(jié)認(rèn)識的根本來源是實踐。在學(xué)習(xí)作為具體科學(xué)的信息學(xué)時，應(yīng)該要做到不唯書、不唯上、只唯實，在生活實踐不斷地獲取經(jīng)驗、認(rèn)識，并用這些經(jīng)驗、認(rèn)識去解決問題（回歸實踐）。從長遠(yuǎn)來看，信息學(xué)的前進(jìn)也只能依靠的不斷實踐。這題目的產(chǎn)生、解決可以說是新穎的，因為這道題目是源于洗衣生活，同時我也利用生活經(jīng)驗來解決。我希望在信息學(xué)競賽中能有這種類型的題目。代碼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-