第 5 天 #
牛客 | 简单的排序 #
洛谷 | 「EZEC-10」排列排序 #
题目
P7714 「EZEC-10」排列排序
题目描述
给你一个长度为 $n$ 的排列 $p_1,p_2, \cdots ,p_n$。你需要把它排序。
每次可以花区间长度，即 $r-l+1$ 的代价，选择排列中的任意一段区间 $[l,r]$，并将 $[l,r]$ 从小到大排序。
现在你可以让他进行若干次这个操作，直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序，即对于 $1$ 到 $n$ 的每一个 $i$，都有 $p_i=i$。
求问花的代价最少为多少？
输入格式
本题有多组询问，第一行有一个数 $T$ 表示询问组数。
对于每组询问：
第一行给出一个整数 $n$。
第二行 $n$ 个整数，由空格隔开，代表排列 $p$ 中元素的值。
输出格式
$T$ 行，每行一个整数表示一组询问的答案。
输入输出样例 #1
输入 #1
2 3 1 3 2 4 3 2 1 4输出 #1
2 3说明/提示
【样例 $1$ 说明】
对于第一组数据，可选择区间 $[2,3]$ 进行排序。
对于第二组数据，可选择区间 $[1,3]$ 进行排序。
【数据规模与约定】
对于 $20%$ 的数据，$n\leq 4$。
对于另 $30%$ 的数据，$\sum n\leq5000$。
对于另 $10%$ 的数据，$p_1=n$。
对于 $100%$ 的数据，$1\le T,\sum n\le 10^6$。
力扣 | 数组的相对排序 #
题目描述
题目描述
给你两个数组，
arr1和arr2，arr2中的元素各不相同，arr2中的每个元素都出现在arr1中。对
arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。
示例 1：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] 输出：[22,28,8,6,17,44]
提示：
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2中的元素arr2[i]各不相同arr2中的每个元素arr2[i]都出现在arr1中