[BeiJing2011]双端队列
时间: 2023-11-30 17:33:18 浏览: 27
引用:每一个双端队列的数对应原序列的下标都是先下降后增加的。题目要求最后的所有序列也是有序的,所以可以求出最后的序列(即排序后的序列),然后分成许多份,要求每一份都是一个双端序列,求最少分成多少份。
对于这个问题,我们可以先将原序列按照数值大小进行排序,然后从头到尾遍历排序后的序列。我们可以使用贪心的策略来选取一段一段的双端队列,使得每个双端队列中的数对应的原序列下标都是先下降后增加的。具体的算法如下:
1. 将原序列按照数值大小进行排序,得到排序后的序列。
2. 初始化一个变量res为1,表示初始至少需要分成一份双端队列。
3. 初始化变量last为n-1,表示上一段双端队列的最后一个数对应的原序列下标。
4. 初始化变量dir为-1,表示上一段双端队列的下降趋势。
5. 从头到尾遍历排序后的序列,使用变量i表示当前位置。
6. 在每次遍历过程中,找到与当前数值相同的一段区间,使用变量j表示这段区间的末尾位置+1。
7. 如果dir为-1,表示上一段双端队列的趋势是下降的,那么判断last是否大于这段区间的最后一个数对应的原序列下标maxp。如果是,则更新last为这段区间的第一个数对应的原序列下标minp;如果不是,则更新dir为1,并更新last为这段区间的最后一个数对应的原序列下标maxp。
8. 如果dir为1,表示上一段双端队列的趋势是上升的,那么判断last是否小于这段区间的第一个数对应的原序列下标minp。如果是,则更新last为这段区间的最后一个数对应的原序列下标maxp;如果不是,则将当前段双端队列分割,并更新res为res+1,更新dir为-1,并更新last为这段区间的第一个数对应的原序列下标minp。
9. 更新遍历位置i为j,即跳过这段区间。
10. 输出res,即最少需要分成的双端队列的份数。