A93506.困牛排序
普及+/提高
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
有 N 头奶牛,编号是 1 到 N。它们现在站成一排,从 Welcome24ever 面前往后依次是:
队列=[p1,p2,…,pN]。
Welcome24ever 想把它们排成标准顺序:
[1,2,3,…,N](也就是 1 号离 Welcome24ever 最近)。
但是奶牛很困:任何时刻,只有最前面那头奶牛(也就是当前站在 Welcome24ever 面前的那头)会听 Welcome24ever 的指令。
一次操作中,Welcome24ever 可以对最前面的奶牛下命令,让它向队伍后面移动 k 步(1≤k≤N−1):
- 这头奶牛会往后走,跨过前方的 k 头奶牛;
- 被跨过的这 k 头奶牛会整体向前挪一格;
- 最终这头奶牛会插到那 k 头奶牛后面。
例如 N=4,队列是 [4,3,2,1]。
如果让最前面的奶牛 4 往后走 2 步,那么队列会变为 [3,2,4,1]。
你的任务是:用最少的操作次数把队列变成 [1,2,…,N],并输出一种最优的操作方案。
输入格式
第一行一个整数 N。
第二行 N 个整数 p1,p2,…,pN,表示初始队列(它是 1 到 N 的一个排列)。
输出格式
第一行输出一个整数 K:最少需要的操作次数。
第二行输出 K 个整数 c1,c2,…,cK(每个都满足 1≤ci≤N−1):
- 第 i 次操作时,让当时最前面的奶牛往后走 ci 步。
如果有多种最优方案,输出任意一种都可以。
输入输出样例
输入#1
4 1 2 4 3
输出#1
3 2 2 3
说明/提示
数据范围
- 1≤N≤105
- [p1,p2,…,pN] 是 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]。