#10698. D - Permutation Subsequence 排列子系列 比赛编号352
D - Permutation Subsequence 排列子系列 比赛编号352
时间限制: 2秒 / 内存限制: 1024MB
得分: 425分
问题描述
给定一个排列 P = (P₁, P₂, ..., PN),这是一个 1 到 N 的排列。
一个长度为 K 的索引序列 (i₁, i₂, ..., iK) 被称为 好索引序列,如果它满足以下两个条件:
- 1 ≤ i₁ < i₂ < ... < iK ≤ N。
- 子序列 (Pᵢ₁, Pᵢ₂, ..., PᵢK) 可以通过重新排列一些连续的 K 个整数得到。更正式地说,存在一个整数 a,使得 {Pᵢ₁, Pᵢ₂, ..., PᵢK} = {a, a+1, ..., a+K-1}。
要求你找到所有好索引序列中,iK - i₁ 的最小值。
可以证明,在本题的约束条件下,至少存在一个好索引序列。
输入
输入从标准输入给出,格式如下:
N K
P₁ P₂ ... PN
- 第一行包含两个整数 N 和 K,表示排列的长度和所求的子序列的长度。
- 第二行包含 N 个整数 P₁, P₂, ..., PN,表示排列 P。
输出
输出一个整数,表示所有好索引序列中 iK - i₁ 的最小值。
样例输入 1
4 2
2 3 1 4
样例输出 1
1
解释:好索引序列包括 (1, 2), (1, 3), (2, 4)。例如,(i₁, i₂) = (1, 3) 是一个好索引序列,因为 1 ≤ i₁ < i₂ ≤ N 且 (Pᵢ₁, Pᵢ₂) = (2, 1) 是连续整数 1, 2 的重新排列。
在这些好索引序列中,最小的 iK - i₁ 的值是 (1, 2),即 2 - 1 = 1。
样例输入 2
4 1
2 3 1 4
样例输出 2
0
解释:在所有的好索引序列中,iK - i₁ = i₁ - i₁ = 0。
样例输入 3
10 5
10 1 6 8 7 2 5 9 3 4
样例输出 3
5
约束
- 1 ≤ K ≤ N ≤ 2 × 10⁵
- 1 ≤ Pᵢ ≤ N 且 Pᵢ ≠ Pⱼ 当 i ≠ j。
- 所有输入值均为整数。
题目分析
该问题要求我们找到最小的 iK - i₁,其中的 i₁, i₂, ..., iK 表示一个 "好索引序列"。要解决这个问题,我们需要:
- 维护一个合适的子序列,在每次检查 Pᵢ 时,快速找出是否能形成一个符合条件的好索引序列。
- 找到连续的 K 个整数,即找到一个合适的区间,使得这个区间内的值是连续的,且尽可能缩短该区间的长度。
由于数组的大小可能高达 2 × 10⁵,所以我们需要设计高效的算法来处理这个问题。