论文标题
用队列改善订单
Improving Order with Queues
论文作者
论文摘要
耐心排序分类数字的顺序，并根据第一个第一（FIFO）原理的排队数量最少。更确切地说，如果输入序列最长的描述子序列的长度为$ L $，则耐心排序使用$ L $ queues。我们问有多少可以通过$ k $ queues（$ k <l $）改善订单？我们解决了这两个分类度量的问题：向下台词的数量和最长的描述子序列的长度。对于第一个措施，我们提供了最佳算法。对于第二个措施，我们给出了一种将LDS从$ L $减少到$ L -K + 1 $的算法，我们提供的序列具有LDS $ L $，该序列无法将其降低到低于$ l -k + 1 $的LDS $ l -k + 1 $，并使用$ k $ queues。此外，我们研究了两个数字序列的合并性，为两个队列的最佳线性算法提供了LDS $ \ \ leq 2 $的最佳线性算法。这项研究的灵感来自于汽车制造中出现的问题。
Patience Sort sorts a sequence of numbers with a minimal number of queues that work according to the First-In-First-Out (FIFO) principle. More precisely, if the length of the longest descreasing subsequence of the input sequence is $L$, then Patience Sort uses $L$ queues. We ask how much one can improve order with $k$ queues, where $k < L$? We address this question for two measures of sortedness: number of down-steps and length of the longest descreasing subsequence. For the first measure, we give an optimal algorithm. For the second measure, we give an algorithm that reduces the LDS from $L$ to $L - k + 1$, and we provide a sequence with LDS $L$ that can't be reduced to an LDS lower than $L - k + 1$ with $k$ queues. Moreover, we study the mergeability of two sequences of numbers, providing an optimal linear algorithm for two queues with LDS $\leq 2$. The research was inspired by a problem arising in car manufacturing.
