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]$,并输出一种最优的操作方案。
$队列=[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$ 的一个排列)。
第二行 $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$ 步。
如果有多种最优方案,输出任意一种都可以。
第二行输出 $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]$。
- $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]$。