[HUSTFC 2023] 排列排序问题
题目描述
JokerShaco 有一个长度为 n n n 的排列 p p p，他认为一个排列必须是有序的，所以他打算将其进行排序。
他可以对这个排列进行如下操作：
- 将这个排列切割成若干个序列（也可以不切割，保持原样），每个序列至少含有一个元素；
- 选择其中一些序列并将它们翻转；
- 将这些序列按照他的意愿重新组合拼接得到一个新的排列。
JokerShaco 认为切割操作非常累，他想知道如果必须把这个排列变得有序，至少需要切割多少次。
一个长度为 n n n 的排列的定义为，包含从 1 1 1 到 n n n 这 n n n 个不同的整数的序列，每个整数恰好出现一次。
序列翻转的定义为，假设存在一个长度为 m m m 的序列 [ a 1 , a 2 , … , a m − 1 , a m ] [a_1,a_2,\dots,a_{m-1},a_m] [a1,a2,…,am−1,am]，那么将这个序列翻转后将会得到 [ a m , a m − 1 , … , a 2 , a 1 ] [a_m,a_{m-1},\dots,a_2,a_1] [am,am−1,…,a2,a1]。
输入格式
第一行包含一个整数 n ( 1 ≤ n ≤ 1 0 6 n\ (1\le n\le 10^6 n (1≤n≤106)，表示排列 p p p 的长度。
第二行包含 n n n 个整数，其中第 i i i 个整数定义为 p i p_i pi。保证输入的 p p p 一定是长度为 n n n 的排列。
输出格式
输出一个整数，表示将排列 p p p 变得有序所需的最少切割次数。
样例 #1
样例输入 #1
5
1 2 3 5 4
样例输出 #1
1
样例 #2
样例输入 #2
3
3 2 1
样例输出 #2
0
Scratch实现
后续
接下来我会不断用scratch来实现信奥比赛中的算法题、Scratch考级编程题实现、白名单赛事考题实现，感兴趣的请关注，我后续将继续分享相关内容
标签：排列,信奥,am,样例,整数,序列,长度,打卡,图形化 From： https://blog.csdn.net/rogeliu/article/details/140208828