赞hft777,我们今天的功臣,哎,我就太悲剧了,这种数据结构题应该是我的长项,但也想偏了
具体如下:
sum[i]存0-i位置的和,那i - j平均值大于a即sum[j]-sum[i]/(j-i)>a
即sum[j]-sum[i]>(j-i)*a,即sum[j]-a*j>sum[i]-a*i
重新构造数组c,c[i] = sum[i]-a*i,将其reverse,然后...
纯逆序问题,要merge哪,或离散化线段树哪,或树状数组都可.....
 

• Re:第六题 (3) sybil_0603 2008-09-20 18:21:27
• Re:第六题 (64) chnming 2008-09-21 09:41:03
  • Re:第六题 (2) ACM_henry 2008-09-21 11:02:31