[BZOJ 2457] 双端队列 (思维)

BZOJ 2457 BZOJ 2457 双端队列


Descriptionmathcal{Description}
Sherry现在碰到了一个棘手的问题,有N个整数需要排序。
Sherry手头能用的工具就是若干个双端队列。

她需要依次处理这N个数,对于每个数,Sherry能做以下两件事:
1.新建一个双端队列,并将当前数作为这个队列中的唯一的数;
2.将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后,Sherry将这些队列排序后就可以得到一个非降的序列。


Solutionmathcal{Solution}

处理到最后 一定是排好序的 递增 数列, 且这个数列由若干 双端队列 构成,

双端队列 的构成顺序决定了该队列中数字编号变化规律为   >递减 ->递增 字形.

于是可以把数组排好序, 然后将其分为数量尽量少的双端队列即可.


Codemathcal{Code}


原文地址:https://www.cnblogs.com/zbr162/p/11822577.html