标签:二分答案

OI

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

cgazn阅读(157)评论(0)赞(0)

题面 题目求平均数最大的子段, 有长度下限m. 转化为答案判定, 就是对于给定的平均数aver, 能否找到一个长度不小于m的满足平均数不小于aver的子段. 把整个数组减去aver, 就变成了判断有没有和为非负的子段. 若有非负子段, 则a...

OI

[洛谷P1462]通往奥格瑞玛的道路[二分答案]

cgazn阅读(82)评论(0)赞(0)

这道题要求最大收费点的最小值,明显是二分答案 二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点 能则缩小maxf, 否则只能是更大的maxf 具体实现: dijkstra松弛的时候加个判断 点权小于...