← 返回题单
题单练习 树状数组
← 上一题 下一题 →

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++ 编辑器
输入
输出