概述
题目传送门
VFleaKing又来了…
考试的时候直接优先队列，最大数据开O2跑了
19
s
19s
19s…
一共
m
m
m个操作，要取最大值操作…怎么搞？
每次，被切断的蚯蚓是最长的，那么将他切掉，分成的两部分分别放到队列里，就可以发现这两个队列都是单调的…
于是，将原蚯蚓作为一个队列，从大到小加入。操作中，在这三个队列中取最大值。
对于增加长度，每次只有两条，也就是被切断后新产生的两条蚯蚓不增加长度，就可以所有蚯蚓统一新增的长度，然后把这两个蚯蚓减去这个长度，单调性仍然成立。
单调性证明如下：
如果有两条长
x
，
y
x，y
x，y的蚯蚓先后被切，一定有
x
≥
y
xge y
x≥y。
长度为
x
x
x的蚯蚓切完变成
a
，
b
a，b
a，b两段，
a
=
p
x
，
b
=
x
−
p
x
a=px，b=x-px
a=px，b=x−px
设切断
x
x
x到切断
y
y
y经历了
t
t
t时间。
切断后，长度为
y
y
y的蚯蚓切完变为
c
，
d
c，d
c，d两段。
c
=
p
(
y
+
t
q
)
，
a
=
p
x
+
t
q
c=p(y+tq)，a=px+tq
c=p(y+tq)，a=px+tq
a
−
c
=
p
x
+
t
q
−
p
y
−
p
t
q
=
p
(
x
−
y
)
+
t
q
(
1
−
p
)
>
0
a-c=px+tq-py-ptq=p(x-y)+tq(1-p)>0
a−c=px+tq−py−ptq=p(x−y)+tq(1−p)>0成立
同理，被切成
1
−
p
1-p
1−p的部分也符合单调性，都是单调递减的。
时间
O
(
n
log
2
n
+
m
)
O(nlog_2 n+m)
O(nlog2n+m)
Code
最后
以上就是标致太阳为你收集整理的[NOIP] [单调队列] NOIP2016Day2 蚯蚓的全部内容，希望文章能够帮你解决[NOIP] [单调队列] NOIP2016Day2 蚯蚓所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![[NOIP] [单调队列] NOIP2016Day2 蚯蚓](/uploads/reation/bcimg7.png)
发表评论 取消回复