我们发现,对于队列来讲,同加,减是不改变这个队列的大小关系的;
但是呢,切开蚯蚓以及新蚯蚓不加是会改变这个队列的大小关系的。
一种简单的想法是 priorityprioritypriority _ queuequeuequeue
另一种是把切出来的两条蚯蚓隔离开,发现每次都会切出两种类型的蚯蚓,一种长的和一种短的。(因为是按比例切割)
那么把这两条蚯蚓放到两个队列当中,就能够隔离这两只蚯蚓,从而起到保护主队单调性的作用
问题是要不要用 priorityprioritypriority _ queuequeuequeue 。
我们发现,在队列一和队列二当中,相邻的两个元素总是紧接着放进去的
问题来了,这两条蚯蚓来自哪里?
答案是原来所有蚯蚓中第一大和第二大的蚯蚓,显然这两条蚯蚓是这两条蚯蚓同一比例的后代
所以前面的蚯蚓就自然大于后面的蚯蚓,因此就删去了 priorityprioritypriority _ queuequeuequeue 这个操作。
那么我们可以证明,这样处理的三个队列(主队,长蚯蚓队,短蚯蚓队)都是单调的,也就是队头大于等于该队的所有元素。
最后就是,我们不能每次都加上一个 qqq (显然是找 ttt )我们假装这个蚯蚓在取出的一瞬间长大了( i−1i-1i−1 )* qqq ( iii 为秒数)然后塞回去的时候在减去 iii * qqq 即可
(注:必须加上( i−1i-1i−1 )* qqq ,不然向下取整精度会不准)