题解 P1514 【引水入城】

· · 题解

思路各位大佬讲的都很明白了

蒟蒻就补个证明帮大家理理思路吧

摘自 大大大蒟蒻我の博客

欲证： 对于第一行的每个水库 x_{i} 流出的水， 他能覆盖的最后一行情况必然是一个连续的区间

反证法：

假设存在一种情况使得覆盖情况如下， 覆盖不连续： 假设蓝色覆盖路线如下： 因为右边红色被覆盖了， 所以从红色水库到下方必然有一条路径 发现路径必有交（紫色部分）， 所以红色水库的水也会流入蓝色那部分， 假设不成立

故一座水库能覆盖的最后一行必然是一个连续的区间

证毕。

全文

upd 2019.11.11

我已经退役啦， 看到评论说的的， 证明确实有不足， 这里进行补充

引用评论区@Asurudo：（感谢这位小伙伴）

@Asurudo ：“如果蓝色那部分干旱区很高，没有水流可以流到，则红色的水流可分叉。有一个样例就是这种情况，如果用这个结论去把区间当作连续的做，则红色可以流到本来流不到的地方。所以用此结论的前提是干旱区都能流到，否则不能用！”

S9咱又夺冠啦！希望我高考也能顺利哈。