The Best Lineup

题目描述

农夫 John 有 $N$（$1 \leq N \leq 2 \cdot 10^5$）头奶牛排成一列 $a$。 队列 $a$ 从前往后第 $i$ 头奶牛的标签是整数 $a_i$（$1 \leq a_i \leq N$）。多头奶牛可能拥有相同的标签。 FJ 将按如下方式构造另一条队列 $b$： 最初，$b$ 为空。 当 $a$ 非空时，移除 $a$ 最前面的奶牛，并选择是否将该奶牛加入到 $b$ 的末尾。 FJ 希望构造队列 $b$，使得 $b$ 中从前到后的标签序列按字典序最大（见脚注）。 在 FJ 构造队列 $b$ 之前，他最多可以进行一次如下操作： 选择队列 $a$ 中的一头奶牛，将其移动到其当前位置之前的任意位置。 在 FJ 最优地至多进行一次上述操作的前提下，输出他能够得到的按字典序最大的 $b$ 的标签序列。 每个输入包含 $T$（$1 \leq T \leq 100$）个相互独立的测试用例。

输入格式

第一行包含 $T$。 每个测试用例的第一行包含 $N$。 每个测试用例的第二行包含 $N$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_N$。 保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，在新的一行输出按字典序最大的 $b$。

3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1

4 3 3 2 1
6 5 4
4 3 2 1 1

提示

在第一个测试用例中，FJ 可以将第五头奶牛移动到紧接在第二头奶牛之后。 此时，$a = [4, 3, 3, 2, 1]$。可以证明 $[4, 3, 3, 2, 1]$ 也是按字典序最大的 $b$。 在第二个测试用例中，FJ 可以将第四头奶牛移动到队列最前面。 在第三个测试用例中，FJ 不需要进行任何操作。他可以通过将除第二头奶牛外的每头奶牛加入到 $b$ 的末尾来构造 $b$。可以证明这样得到的 $b$ 按字典序最大。 SCORING: Inputs 2-4: $N \leq 100$ Inputs 5-8: $N \leq 750$ Inputs 9-18: 无额外限制 FOOTNOTE: 回顾：当且仅当满足以下条件之一时，序列 $s$ 按字典序大于序列 $t$： 在第一个满足 $s_i \neq t_i$ 的位置 $i$，有 $s_i > t_i$。 如果不存在这样的 $i$，则 $s$ 的长度大于 $t$。 题目鸣谢：Chongtian Ma, Haokai Ma, Andrew Li

标签: USACO|2025|Silver

来源

USACO|2025|Silver