gougou1027
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
1027
Fill the Cisterns!
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1389
9 2006-08-21 19:42:37 00:07:32 8968K C++ glimpse
大家知道什么叫暴殄天物吗？知道什么叫不会做的题cheat过吗？我的1027就非常符合这两条。
我开了一个数组v[1000 * 1000 + 40002]，然后模拟，v[i]代表前i层的储水量。然后while(v[i]<V){i++}。虽然手段粗暴了点，倒是瞬间秒杀了。
ZZT这道题又是第一，很奇妙吧，作为ACM的队友，我们的风格迥异，他总是ranklist的前几名，而我总是后几名。
----
正确而简单的做法是二分答案，也就是水的高度，那么这些水的体积是非常容易在O(n)求出来的。复杂度O(lg((r-l)/eps)*n)
实际如果二分多少个是满的，或做非空的，那么也可以做到O(n*lgn)，不过这是后求水的体积要麻烦得多。1027
Fill the Cisterns!
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1389
9 2006-08-21 19:42:37 00:07:32 8968K C++ glimpse
大家知道什么叫暴殄天物吗？知道什么叫不会做的题cheat过吗？我的1027就非常符合这两条。
我开了一个数组v[1000 * 1000 + 40002]，然后模拟，v[i]代表前i层的储水量。然后while(v[i] ZZT这道题又是第一，很奇妙吧，作为ACM的队友，我们的风格迥异，他总是ranklist的前几名，而我总是后几名。
正确而简单的做法是二分答案，也就是水的高度，那么这些水的体积是非常容易在O(n)求出来的。复杂度O(lg((r-l)/eps)*n)
实际如果二分多少个是满的，或做非空的，那么也可以做到O(n*lgn)，不过这是后求水的体积要麻烦得多。