题库练习 困牛排序
← 上一题 下一题 →

A6907 | 困牛排序

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $N$ 头奶牛,编号是 $1$ 到 $N$。它们现在站成一排,从 Welcome24ever 面前往后依次是:

$队列=[p_1,p_2,\dots,p_N]$。

Welcome24ever 想把它们排成标准顺序:

$[1,2,3,\dots,N]$(也就是 1 号离 Welcome24ever 最近)。

但是奶牛很困:任何时刻,**只有最前面那头奶牛**(也就是当前站在 Welcome24ever 面前的那头)会听 Welcome24ever 的指令。

一次操作中,Welcome24ever 可以对最前面的奶牛下命令,让它向队伍后面移动 $k$ 步($1\le k\le N-1$):
- 这头奶牛会往后走,跨过前方的 $k$ 头奶牛;
- 被跨过的这 $k$ 头奶牛会整体向前挪一格;
- 最终这头奶牛会插到那 $k$ 头奶牛后面。

例如 $N=4$,队列是 $[4,3,2,1]$。
如果让最前面的奶牛 $4$ 往后走 $2$ 步,那么队列会变为 $[3,2,4,1]$。

你的任务是:用**最少**的操作次数把队列变成 $[1,2,\dots,N]$,并输出一种最优的操作方案。

输入格式

第一行一个整数 $N$。
第二行 $N$ 个整数 $p_1,p_2,\dots,p_N$,表示初始队列(它是 $1$ 到 $N$ 的一个排列)。

输出格式

第一行输出一个整数 $K$:最少需要的操作次数。

第二行输出 $K$ 个整数 $c_1,c_2,\dots,c_K$(每个都满足 $1\le c_i\le N-1$):
- 第 $i$ 次操作时,让当时最前面的奶牛往后走 $c_i$ 步。

如果有多种最优方案,输出任意一种都可以。

输入输出样例

输入 #1
4
1 2 4 3
输出 #1
3
2 2 3
C++ 编辑器
输入
输出