> 温馨提示:思路来自洛谷题解,并非本人.
祝大家CSP考试顺利!
这道题的主要思路如下:
1.看最强的蛇吃完后会不会变成最弱的蛇.
如果不会变成最弱的蛇,就放心吃,因为吃完后下一条最强的蛇肯定比原来的它弱,而最弱的蛇肯定比原来的强,所以一定不会吃到它.
2.如果吃了后会成最弱的蛇,那就要复杂的考虑了(本题的最难点):
它就得考虑下一条蛇吃完它后会不会变成最弱的蛇,如果不会就不吃,否则又得考虑下下一条蛇吃完下一条蛇会不会变成最弱的蛇,如果不会那下一条蛇就不吃,那它就可以放心吃,否则又得考虑下下下一条蛇……
开始递归了
简单点说就是一直判断,直到有一条蛇可以放心吃了为止(判断奇偶性).
由于这里的时限只有1s,所以不能用洛谷能过的set来做了.
我们可以用双端队列来做这题
建立两个双端队列 q1,q2q1,q2q1,q2,q1q1q1 存储初始的有序蛇,如果吃了以后不是最弱的,就存进 q2q2q2 的头部,让 q2q2q2 也满足单调性。
最大值的话在 q1,q2q1,q2q1,q2 找就行了.