Sleepy Cow Sorting

题目描述

农夫约翰试图在他的 $N$ 头奶牛（$1 \leq N \leq 10^5$，方便起见编号为 $1 \dots N$）出发去牧场吃早饭之前，把它们排好序。 目前，奶牛们站成一排，顺序为 $p_1, p_2, p_3, \dots, p_N$，农夫约翰站在奶牛 $p_1$ 的前面。 他希望重新排列奶牛，使它们的顺序变为 $1, 2, 3, \dots, N$，并且奶牛 $1$ 紧挨着农夫约翰。

今天奶牛们有点困，所以任意时刻，唯一会听从农夫约翰指令的是正对着农夫约翰的那头奶牛。在一个时间步中，他可以指示这头奶牛沿队列向后走 $k$ 步，其中 $k$ 可以是 $1$ 到 $N-1$（含）之间的任意整数。她经过的那 $k$ 头奶牛会向前慢慢挪动，为她腾出位置，使她插入到它们之后。

例如，设 $N=4$，奶牛起始顺序如下： FJ: 4, 3, 2, 1 此时唯一注意 FJ 的是奶牛 $4$。如果他指示她向后走 $2$ 步，那么顺序将变为： FJ: 3, 2, 4, 1 现在唯一注意 FJ 的是奶牛 $3$，因此在第二个时间步他可以给奶牛 $3$ 下达指令，如此继续直到奶牛排好序。

农夫约翰急于尽快完成排序，这样他就能回到农舍吃自己的早饭。请帮助他找到一组指令序列，使奶牛在最少的时间步内排好序。

输入格式

第一行输入 $N$。 第二行输入 $N$ 个用空格分隔的整数： $p_1, p_2, p_3, \dots, p_N$，表示奶牛的初始顺序。

输出格式

第一行输出一个整数 $K$，表示将奶牛排好序所需的最少时间步数。 第二行输出 $K$ 个用空格分隔的整数 $c_1, c_2, \dots, c_K$，每个都在范围 $1 \ldots N-1$ 之内。 此外，若在第 $i$ 个时间步中，FJ 指示正对着他的奶牛向后移动 $c_i$ 步，那么在经过 $K$ 个时间步后，奶牛应当处于排好序的状态。 如果存在多种最优的指令序列，你的程序可以输出其中任意一种。

4
1 2 4 3

3
2 2 3

提示

题目致谢：Dhruv Rohatgi

标签: USACO|2019|Gold

来源

USACO|2019|Gold