[POJ2018][洛谷P1404]平均数/Best Cow Fences[二分答案]

题面

题目求平均数最大的子段, 有长度下限m.

转化为答案判定, 就是对于给定的平均数aver, 能否找到一个长度不小于m的满足平均数不小于aver的子段.

把整个数组减去aver, 就变成了判断有没有和为非负的子段. 若有非负子段, 则aver还可以往大猜;否则aver要变小.

所以问题最终转化为了求最大连续子段和, 而连续字段和可以化为前缀和相减的形式.

因此所求即为:

$$\max_{m<=i<=n}\{S_i-\min_{1<=j<=i-m}\{S_j\}\}$$

注意到i每变化1时j上界增加一, 下界不变, 只要用一个变量不断更新$latex S_j$的最大值即可.

特别注意: 实数域上的二分, 要求保留k位小数, eps一般取1e-(k+2), 精度太高也会WA.也可以采用固定次数循环的二分方法.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址