Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

想到证明了,可以在O(n)的时间求出一个序列的长度>=k的平均值最大的子串: 见内

Posted by rruucc at 2003-11-04 09:30:00 on Problem 1387
In Reply To:rruucc的算法是n^3的,但是我怀疑是错的,我多出些数据试试 Posted by:hawk at 2003-11-03 17:25:38

假设当前有:
n2<n1 pa2>pa1
n1 n2为串长; pa1 pa2为当前平均值
当添加了和为a 长为x 的子串后平均值分别为:
p1=(n1*pa1+a)/(n1+x); p2=(n2*pa2+a)/(n2+x)
我的算法里假设p2>=p1或者pa2就是最大值,
否则,有p1>p2且p2>pa2且a>0
   或者p1>p2且p1>pa2>p2且a>0
两者都可以推出矛盾

应该有更高等更容易理解的证明 我在想想

Followed by:

Post your reply here:

Home Page Go Back To top