算法笔试模拟题精解之“Codancer 的数组封印”

算法笔试模拟题精解之“Codancer 的数组封印”

贡献者 | 猿圈

简介：我们逆向思考，对于给定的数组每次删去一个数，相邻两次操作的答案不

会超过 1。

题目描述

等级：困难

知识点：DP、LIS

查看题目：Codancer 的数组封印

Tom 有一个长度为 n 的排列数组 a，即 a 中的每个数字的范围都在 [1,n] 中并且

每个数字都不重复。但是现在 Codancer 把整个数组给封印了！

现在 Codancer 给了 Tom 一个解封序列 b, 即 bi 代表第 i 次解封 a[b[i]]。

接下来 Tom 每次都会解封一个位置的数字，令 L[i] 代表第 i 次解封后所

有被解封的数字构成的数组的 LIS 的长度，现在 Codancer 想让 Tom 计算

L[1]+L[2]+L[3]+…+L[n] 的值是多少？

第一行是一个正整数 n，代表 a 数组和 b 数组的长度，接下来第一行输入数组

a，第二行输入数组 b。(1<=n<=50000)

输出 L[1]+L[2]+…+L[n] 的值。

示例 1

输入：

4

[4,2,1,3]

[1,2,4,3]

输出：

6

注意

L[1]=1 解封后为 {4}

L[2]=1 解封后为 {4,2}

L[3]=2 解封后为 {4,2,3}

L[4]=2 解封后为 {4,2,1,3}

解题方法：

第一步解封后数组为 {4}，因此 L[1]=1

第二步解封后数组为 {4,2}，因此 L[2]=1

第三步解封后数组为 {4,2,3}，因此 L[3]=2

第四步解封后数组为 {4,2,1,3}，因此 L[4]=2

因此 L[1]+L[2]+L[3]+L[4]=6

红色数字构成的序列即为 LIS。

我们逆向思考，对于给定的数组每次删去一个数，相邻两次操作的答案不会超

过 1，

对于第 i 次操作我们随便求一个 LIS, 如果第 i+1 次操作删除的数字在这个 LIS 内，

我们就要重新求 LIS, 否则答案保持不变，由于随机生成的全排列 LIS 长度的期

望为 sqrt(n)，因此最多计算 sqrt(n) 次 LIS。

时间复杂度：O(nsqrt(n)*log(n))。

看完之后是不是有了答题思路了呢，快来练练手吧：Codancer 的数组封印