OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【CQOI2014】排序机械臂

【题目描述】

SORT公司是一个专门为人们提供排序服务的公司,该公司的宗旨是:“顺序是最美丽的”。他们的工作是通过一系列移动,将某些物品按顺序摆好。他们的工作规定只能使用如下方法排序:

先找到编号最小的物品的位置P1,将区间[1,P1]反转,再找到编号第二小的物品的位置P2,将区间p[2,P2]反转……


上图是有6个物品的例子,编号最小的一个是在第4个位置。因此,最开始把前面4个物品反转,第二小的物品在最后一个位置,所以下一个操作是把2-6的物品反转,第三部操作是把3-4的物品进行反转……

在数据中可能存在有相同的编号,如果有多个相同的编号,则按输入的原始次序操作。

【输入】

输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000。第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号。

【输出】

输出共一行,N个用空格隔开的正整数P1,P2,P3…Pn(1<=Pi<=N),Pi表示第i次操作前第i小的物品所在的位置。注意:如果第i次操作前,第i小的物品己经在正确的位置Pi上,我们将区间[Pi,Pi]反转(单个物品)。

【输入样例】

6

3 4 5 1 6 2

【输出样例】

4 6 4 5 6 6

【题解】

Splay裸题,维护以每个节点为根的区间里的最小值和最小值的位置,第i次操作时把先把第i-1个节点旋转到根,在右子树内进行操作即可。注意反转时最小值的位置pos会变为sz-pos+1,其中sz表示区间大小。

还是忍不住吐槽一下,BZOJ上输出答案时最末尾不能有空格,破坏了我1A的计划QAQ

【代码】

状态还不错,第一次没处理反转时最小值的位置,第二次PE,然后就AC了。下次一定要争取1A~

http://paste.ubuntu.com/10768951/

评论
热度(1)

© OI技术宅 | Powered by LOFTER