ioi2007的作业音乐水栅

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-