华师一附中OI组

标题: 2840: 玩具TOY [打印本页]

作者: admin 时间: 2021-10-30 07:52
标题: 2840: 玩具TOY
题目描述

哲哲很喜欢玩玩具，在他的强烈要求下，他的爸爸妈妈又给他买了新玩具。这种玩具在买来的时候，原本是独立的n块，并且这n块会有不同的形状。现在哲哲想把这些块连接成一条长链。他的手中始终会握住当前长链玩具的首部，加入第i块( 形状为mi)时，他会写下一个数字ki ，然后将其插入到长链的从首部开始数的第ki个块与第ki+1个块之间,如果ki=0则接到首部之前，如果ki=当前链长度,则接到尾部之后。

但是当他将这个长链玩具接好时，他发现玩具实在太长了，而且全部都缠在了一起，根本不知道是个什么样子。不过幸好他还留着那些写下的数字，现在他想让你根据数字，模拟出长链玩具的最终形态（即最终的m序列）。

输入格式
第一行一个正整数n。
以后n行，每一行两个正整数ki和mi,如上文所述。

输出格式
仅一行，输出从长链的首部到尾部的每个块的形状。

输入样例
4
0 7
1 5
1 3
2 6
输出样例复制
7 3 6 5

数据范围与提示
首先7在第一个，然后把5插到7后变成7 5，在把3放到7后变成7 3 5，在把6插到3后变成7 3 6 5.

对于 20\%的数据，n \leq 5000n≤5000。

对于 50\%的数据，n \leq 50000n≤50000。

对于 100\%的数据，n \leq 300000n≤300000，m_i \leq 500000m
i

≤500000。

作者: admin 时间: 2021-11-8 10:31
考察点：逆向思维，数据结构维护。

1、直接模拟，用数组存，每次加入后把其他数往后移。

2、给各种加break、揣摩数据的乱搞qwq。

3、虽然实际情况是按时间顺序向长链中插入元素，但是随着元素的插入，链也不断发生着变化，这样除了模拟之外没有其他很好的算法。所以，我们不妨用逆向思维去思考这个问题。
如果是逆着插入点，首先，对于每一个元素i,在它之前必有ki-1个空元素（也就是在它之前插入的未知元素），而且对于最后插入的那个元素n，它的最终位置必为kn+1, 并且不会再发生移动。

再来考虑插入的第n-1个元素：

① 如果kn-1<kn，那么第n个元素的插入不会影响到它的最终位置，所以它的最终位置为kn-1+1，满足它之前有kn-1-1个空元素。

② 如果k[n-1]>=k[n]，如果它仍然要插在k[n-1]+1的位置，那么第n个元素的插入使它

之前的空元素个数为$k[n-1]-2$,小于$k[n-1]-1$。这样会导致在它之前插入的点的个数大于所能提供的位置数，则它必须插在之前有$k[n-1]-1$个空元素的位置，也就是$k[n-1]+2$。

然后对于这之前的每一个元素i，都必须插在之前有ki-1个空元素的位置（当然那个位置也要为空），所以只要从头开始数，数到有ki个空元素的位置，将其插入。
朴素算法是$O(n^2)$的，所以可以用树状数组维护。（线段树也可以）

欢迎光临华师一附中OI组 (http://hsyit.cn/)