试卷排序

题目背景

期末考试临近了，Yurchiu 和 zzw 收到了来自老师的试卷关爱，但是试卷太多了，足足有 $10^{6}$ 张，他们已经无法排好试卷了。

所以在 zzy 的建议下，他们把这个问题交给了你。

题目描述

给定一个页码总数为 $n$ 的试卷堆，现要求你将它进行排序，你有如下两种操作：

选定一张试卷，将之置于试卷堆顶部；
选定一张试卷，将之置于试卷堆底部。

但由于 Yurchiu 和 zzw 的能力不同，所以你需要分别处理。

Yurchiu 希望能将试卷页码从小到大排列，但她只能实行操作 $1$ ;

zzw 的希望与 Yurchiu 相同，但他可以进行操作 $1$ 和操作 $2$ 。

输入格式

第一行一个整数 $n$ 。

第二行一个字符串 $s$ ，表示你将为谁进行试卷排序。

第三行共 $n$ 个整数，分别为 $a_1,a_2,\cdots,a_n$ 表示试卷页码的当前状态。

输出格式

输出共一行一个整数，为最小的操作次数。

样例 #1

样例输入 #1

5
yz
5 1 2 4 3

样例输出 #1

样例 #2

样例输入 #2

5
zzw
5 1 2 4 3

样例输出 #2

提示

【数据范围】

对所有测试点保证 $1 \leq n \leq 10^{6}$ ， $1 \leq a_i \leq n$ 。

测试点	$n$	$s$
$1 \sim 2$	$=10$	$=\tt{yz}$
$3 \sim 4$	$=10^{3}$	$=\tt{yz}$
$5 \sim 8$	$=10^{6}$	$=\tt{yz}$
$9 \sim 10$	$=10$	$=\tt{zzw}$
$11 \sim 12$	$=10^{3}$	$=\tt{zzw}$
$13 \sim 20$	$=10^{6}$	$=\tt{zzw}$

【本题来源】

Idea & 题面：zzw；
数据：yz；
标程：njy；
验题：lhz；
题解：zzy。

题解

容易发现，Yurchiu 操作即求含 $n$ 的最长连续上升子序列，zzw 操作即求最长连续上升子序列。

连续上升子序列指一个原序列的子序列 $a_1,a_2,\dots,a_p$ ，保证 $\forall i\in[1,p)$ ，有 $a_i=a_{i+1}-1$ 。

$O(n)$ 求之即可。

本文作者：2021 级信息社团

本文链接：https://yz-hs.github.io/63f21f74d510/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划 Idea

最后更新：2023-08-26, 14:24:45

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

[Idea] 试卷排序