A93506.困牛排序

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

NN 头奶牛,编号是 11NN。它们现在站成一排,从 Welcome24ever 面前往后依次是:

队列=[p1,p2,,pN]队列=[p_1,p_2,\dots,p_N]

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

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

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

一次操作中,Welcome24ever 可以对最前面的奶牛下命令,让它向队伍后面移动 kk 步(1kN11\le k\le N-1):

  • 这头奶牛会往后走,跨过前方的 kk 头奶牛;
  • 被跨过的这 kk 头奶牛会整体向前挪一格;
  • 最终这头奶牛会插到那 kk 头奶牛后面。

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

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

输入格式

第一行一个整数 NN
第二行 NN 个整数 p1,p2,,pNp_1,p_2,\dots,p_N,表示初始队列(它是 11NN 的一个排列)。

输出格式

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

第二行输出 KK 个整数 c1,c2,,cKc_1,c_2,\dots,c_K(每个都满足 1ciN11\le c_i\le N-1):

  • ii 次操作时,让当时最前面的奶牛往后走 cic_i 步。

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

输入输出样例

  • 输入#1

    4
    1 2 4 3

    输出#1

    3
    2 2 3

说明/提示

数据范围

  • 1N1051\le N\le 10^5
  • [p1,p2,,pN][p_1,p_2,\dots,p_N]11NN 的一个排列

样例解释

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

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

所以最少操作次数是 K=3K=3,一种方案是 [2,2,3][2,2,3]

首页