当前位置:首页 > 数据结构 > 线段树 > 正文
GDKOI2021普及组Day1B灌水
1097+

题目大意:一个凹凸不平的水槽,要使某个位置水量达到高度y,需要灌多少水?(已知每个位置的水量,多次询问!)

解题思路

暴力程序如下:自该位置开始,左边比他低的和右边比他高的都灌满水。

不难发现,程序满在查找,只要找到第一个大于等于k的位置,就可以用前缀和了。如果区间是[l, r],那么总面积是k*(r-l+1),已有面积是s[r]-s[l-1]。

怎么快速查找第一个大于等于k的位置呢?线段树肯定都可以解决。

以找左边第一个大于等于k为例:结点记录区间最大值,如果存在大于等于k则先找右边,因为右边的更加接近;找到几返回,否则返回左边的答案。

程序实现

当然,使用ST表也可以解决,我可以二分查找这个位置。

普及组同学还可以用分块来做:

多分几块速度更快:

GDKOI2021普及组Day1B灌水:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!