Skip to content

1105: 序列

题目

题目描述

托米有一个长度为 $n$ 的正整数序列 $p_{1 \ldots n}$ ,它们构成了一个 $1$ 至 $n$ 的 排列

托米希望能通过自己的努力,把这个正整数序列变成 $1$ 至 $n$ 的递增序列。可是托米能力有限,他每次只能对整个序列进行以下两种操作之一:

  • 操作一:将排列中的倒数第二个数移至开头,其余的数顺序保持不变;
  • 操作二:将排列开头的第一个数移至结尾,其余的数顺序保持不变。

若干连续的同种操作称为一段。托米希望知道,如果要将初始的正整数序列变成 $1$ 至 $n$ 的递增序列,至少需要 多少段操作一

托米并不会做这个题,所以他求助于你。如果你能帮助他解决此问题,他就会给你的机考成绩加上一百分。

输入格式

第一行包含一个正整数 $n$

第二行包含 $n$ 个空格分隔的正整数 $p_1, p_2, \ldots, p_n$ 表示初始的正整数序列

  • 输入保证每一个 $1$ 与 $n$ 之间整数在第二行出现恰一次

输出格式

输出一行,包含一个整数,表示将初始的正整数序列变成 $1$ 至 $n$ 的递增序列所需的最少 操作一的段数

样例输入

样例输入 1

text 6 2 4 5 1 3 6

样例输入 2

text 8 8 4 7 3 6 2 5 1

样例输出

样例输出 1

text 2

样例输出 2

text 5

样例说明

对于样例 1的一种可行方案:

  • 进行 $5$ 次操作二,序列变成 $6, 2, 4, 5, 1, 3$ ;
  • 进行 $3$ 次操作一,序列变成 $4, 5, 1, 6, 2, 3$ ;
  • 进行 $4$ 次操作二,序列变成 $2, 3, 4, 5, 1, 6$ ;
  • 进行 $1$ 次操作一,序列变成 $1, 2, 3, 4, 5, 6$ .

数据范围

对于 B 班同学:

  • 对于 $5\%$ 的测试数据,满足 $n=3$

  • 对于 $10\%$ 的测试数据,满足 $3\leq n \leq 5$

  • 对于 $20\%$ 的测试数据,满足 $3\leq n \leq 10$

  • 对于 $40\%$ 的测试数据,满足 $3\leq n \leq 20$

  • 对于 $60\%$ 的测试数据,满足 $3\leq n \leq 50$

  • 对于 $100\%$ 的测试数据,满足 $3\leq n \leq 500$

该题与1106是同一题,仅数据范围不同!

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!