Codeforces 609F Frogs and mosquitoes 题解
题意
有$n (1\le n\le 2\cdot10^5)$个青蛙固定在平面直角坐标系中$Ox$的非负半轴上,对于第$i (1\le i\le n)$个青蛙有两个值,分别是$x_i$和$t_i (0\le x_i,t_i\le 10^9)$($x_i$两两不同),$x_i$代表它的位置,$t_i$代表它的舌头的长度。
有$m (1\le m\le 2\cdot10^5)$只蚊子也固定在$Ox$的非负半轴上,对于第$i (1\le i\le m)$只蚊子有两个值,分别是$p_i$和$b_i (0\le p_i,b_i\le 10^9)$,$p_i$代表它的位置,$b_i$代表它的大小。
如果一个青蛙$i$和一只蚊子$j$,满足 $p_j$在区间$[x_i,x_i+t_i]$内,那么青蛙$i$就可以吃掉蚊子$j$,并且舌头会增长$b_j$。如果有多个青蛙可以吃掉同一个蚊子,那么这个蚊子会被$x_i$最小的那个青蛙吃掉。
蚊子是按照输入的顺序降临的,如果第$i$个蚊子要降临,必须满足 青蛙吃光了可能吃掉的所有蚊子$j (1\le j<i)$。
问第$i$只青蛙吃掉了多少蚊子和最后它的舌头有多长。
题解
对于青蛙$i$和$j$,如果$[x_i,x_i+t_i]$包含在$[x_j,x_j+t_j]$中,那么青蛙$i$就永远没有用了。
因为处于区间$[x_i,x_i+t_i]$内的蚊子总会被青蛙$j$吃掉($x_j<x_i$)。
那么大体思路就出来了:
读入青蛙,删除无用的青蛙
依次读入蚊子,每次读入蚊子$i$做出以下操作:
- 如果蚊子$i$不能被如何青蛙吃掉,那么就丢入一个数据结构中,
continue
;否则: - 选用处于最左边的青蛙$j$吃掉蚊子$i$。因为此是青蛙$j$的舌头变长了,所以再删除一遍无用的青蛙 并且 查找青蛙$j$可不可以再吃掉蚊子了。最后更新青蛙$j$的数据。
- 如果蚊子$i$不能被如何青蛙吃掉,那么就丢入一个数据结构中,
输出答案
完成这个过程可以用三个set
完成,分别维护青蛙的$x_i$,$(x_i+t_i)$和目前没有被吃掉的蚊子,有关查找的操作可以用二分完成,具体见程序。时间复杂度$O(n\log{n}+m\log{m})$。
也可以用线段树完成。
程序
1 | // #pragma GCC optimize(2) |