1 条题解
-
0
何老师 (root) LV 0 MOD @ 2020-06-10 07:30:51
这道题是典型的单调队列的题。要把每头奶牛遍历一遍,查找它前后D距离以内的不矮于自身高度2倍的牛。这里做一个推导:如果一个范围以内最高的牛都不够高,那它肯定不会觉得拥挤。
所以,分别找每个奶牛前后D距离内最高的奶牛是否不矮于自身高度2倍,再把觉得拥挤的牛统计起来就可以了。
用一个递减单调队列存每个奶牛,每次入牛时把它前面矮于它的奶牛都踢出,还要把队首所有坐标不在距离D范围以内的奶牛出队,最后判断队首的奶牛是否足够高就完了。
这样遍历前、后各一次,两次都觉得拥挤的奶牛才把它加上。
- 1