测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6907. 困牛排序

编程题 普及+/提高
知识点

题目描述

有 $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

说明/提示

## 数据范围

- $1\le N\le 10^5$
- $[p_1,p_2,\dots,p_N]$ 是 $1$ 到 $N$ 的一个排列


## 样例解释

初始 $队列=[1,2,4,3]$(下标从 $1$ 开始):

- 第 1 次:最前面是 $队列[1]=1$,让它往后走 $2$ 步
结果 $队列=[2,4,1,3]$
- 第 2 次:最前面是 $2$,让它往后走 $2$ 步
结果 $队列=[4,1,2,3]$
- 第 3 次:最前面是 $4$,让它往后走 $3$ 步
结果 $队列=[1,2,3,4]$,排好序了

所以最少操作次数是 $K=3$,一种方案是 $[2,2,3]$。
上一题 去做题 下一题