#10698. D - Permutation Subsequence 排列子系列 比赛编号352

D - Permutation Subsequence 排列子系列 比赛编号352

时间限制: 2秒 / 内存限制: 1024MB

得分: 425分


问题描述

给定一个排列 P = (P₁, P₂, ..., PN),这是一个 1 到 N 的排列。

一个长度为 K 的索引序列 (i₁, i₂, ..., iK) 被称为 ​好索引序列​,如果它满足以下两个条件:

  1. 1 ≤ i₁ < i₂ < ... < iK ≤ N。
  2. 子序列 (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 表示一个 "好索引序列"。要解决这个问题,我们需要:

  1. 维护一个合适的子序列​,在每次检查 Pᵢ 时,快速找出是否能形成一个符合条件的好索引序列。
  2. 找到连续的 K 个整数​,即找到一个合适的区间,使得这个区间内的值是连续的,且尽可能缩短该区间的长度。

由于数组的大小可能高达 2 × 10⁵,所以我们需要设计高效的算法来处理这个问题。