Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

看到的一份不错的解题报告,分享下 ~~不知道那些几百Ms怎么做得?

Posted by zhzz at 2008-09-28 22:57:40 on Problem 2452
假若把这数列分成两段,1,5是其中一段,2,3,4是其中一段,这就能得出结果了。有什么好方法呢?我想到用数组保存其中一段为最小值1,最大值5,的数列,而另一个为最小值2,最大值4的段,这样就能解决了。就是说当读到一个数时,判断下这个数是否比当前所记录的段中的最大值要大,是的话,就会形成一个新的更长的段,如果不是,则另开新段,把这个数记为最小值,最大值设为和最小值相等,这样就肯定对的。
    现在问题算是初步解决了。但是还有个严重的问题,就是时限,如果每读入一个数,都与每个记录段作比较的话,这样会达到O(n^2)的,对于这题规模绝对过不了。这样就开始着手想优化。利用上面的例子,记录一段为{1,5},另一段为{2,4},联想下是不是可以像最长上升子序列那样用二分把复杂度降为 O(nlogn)呢?假设现在读到一个6,则可以把{1,5}段扩长为{1,6},{2,4}段也扩长为{2,6},但2出现在1后,所以{1,6}段肯定比{2,6}段长,而{2,6}段也没必要保留,因为如果读到在{2,6}段中间的数,中间因为出现一个6,对于条件不成立;若读到大于6的数,则可以扩展{2,6}段时{1,6}段同样可以扩展。而当只读了1,5时,存在段{1,5}后,若读到一个3,需要另开新段{3,3},此时若读到6,则依上扩展成段{1,6},并舍弃{3,3}段;若读到一个4,则{1,5}段不可扩展,只能把{3,3}段扩成{3,4}段;若读到一个2,则需要另开新段 {2,2},同时由于{3,3}段后面出现了比最小值更小的数,这段不再保留,只剩下{1,5}和{2,2}。通过简单的例子,大概可以看出保存的最小值是递增的,而保存的最大值是递减的,同时由于当修改某段后,此段以外的段不用修改,因此可以保持很好的性质,可以用二分完成,每输入一个数,先查找最大值,若小于所有的最大值,则需要添加新段,再来查找最小值。这样就可以成功地求出最长距离的满足题目要求的段了。
    写好代码,其实也不长,就1k左右,

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator