codeforces #609 F. Frogs and mosquitoes (线段树+二分)

题目链接

题意:n只青蛙,第i只位于x[i],舌头长度为t[i]。m只蚊子,第i只蚊子所在位置为p[i],蚊子的大小为b[i]。

蚊子按照出现顺序输入。

一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置,或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。

当多只青蛙可以吃到同一只蚊子的时候,最左边的那只青蛙来吃。

当一只青蛙吃掉一只蚊子以后,青蛙的舌头增加蚊子的大小。

当一只青蛙吃掉一只蚊子后,因为舌头边长而又能吃到其他蚊子的时候,这只青蛙会继续吃,只到当前没有蚊子可以被任何一只青蛙吃到,在这个过程之后才会飞来下一只蚊子。

 

思路:问题的关键在于,对于某只蚊子,我们如何找到能吃到该蚊子的青蛙中最左边的那只。

可以抽象成寻找区间[1,r]中,最左边的那个>=x的元素。

联想到一个类似的问题:对于区间[1,n],找到最左边的>=x的元素。做法是线段树维护最大值,只需要每次先query左子树,就可以保证找到额是最左边的。

但是如果是区间[1,r]呢。。。

我们发现。。。区间[1..k] (k<=r)的最大值是随着k的增大而不减的。。。。(最大值。。。肯定不减呀)

也就是说是单调的。。。因此我们可以考虑二分。。。这很重要。。。

寻找区间[1,r]中第一个大于等于x的元素,利用单调性来二分做是一个很经典的做法,复杂度(lgn)^2,注意体会。

 

因此具体做法是:

建树,存的是区间中x[i]+t[i]的最大值。

对于每一只飞来的蚊子,寻找能吃到它的最左边的青蛙的编号(具体做法是,先找到最后一个位置小于等于蚊子位置的青蛙的下标,作为青蛙的下标的上界,然后二分,每次query区间最大值,不断缩小区间。)

当蚊子被吃的时候记录答案,更新青蛙的各种信息(线段树要update)

并且由于青蛙的舌头变长了,可能吃到之前没有青蛙能吃到的蚊子,因此要把之前的没有能被青蛙吃到的蚊子存进一个multiset(因为蚊子可能落在同一个位置) 然后让当前的青蛙尽可能吃这些没有被吃到的蚊子,同时更新青蛙的各种信息,并在multiset中删除这只蚊子/

没被吃的时候就扔进multiset里。

需要注意multiset erase的时候要erase一个迭代器。。。不然会把所有相同的都删掉。。。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz