题解

1 条题解

  • 0
    @ 2020-06-10 07:30:51

      这道题是典型的单调队列的题。要把每头奶牛遍历一遍,查找它前后D距离以内的不矮于自身高度2倍的牛。这里做一个推导:如果一个范围以内最高的牛都不够高,那它肯定不会觉得拥挤。

      所以,分别找每个奶牛前后D距离内最高的奶牛是否不矮于自身高度2倍,再把觉得拥挤的牛统计起来就可以了。

      用一个递减单调队列存每个奶牛,每次入牛时把它前面矮于它的奶牛都踢出,还要把队首所有坐标不在距离D范围以内的奶牛出队,最后判断队首的奶牛是否足够高就完了。

      这样遍历前、后各一次,两次都觉得拥挤的奶牛才把它加上。

  • 1

信息

ID
1709
难度
(无)
分类
图结构 | 最短路差分约束数据结构 | 队列 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者