c - 关于如何找到根据给定条件标记给定数组的所有元素的最少步数的任何提示？

Question

两个整数 N<=10^5和 K<=N给出，其中 N是数组的大小 A[]和 K是我们可以在我们的过程中选择的连续子序列的长度。每个元素A[i]<=10^9 .现在假设最初数组的所有元素都没有标记。在每一步中，我们将选择长度为 K 的任何子序列。如果这个子序列有未标记的元素，那么我们将标记所有未标记的元素，这些元素在后序中是最小的。现在如何计算标记所有元素的最小步骤数？

为了更好地理解问题，请看这个例子——

N=5 K=3 A[]=40 30 40 30 40

第一步-选择区间[1,3]，标记A[1]和A[3]

Step2- 选择区间[0,2]并标记A[0]和A[2]

第三步-选择区间[2,4]并标记A[4]

因此这里的最小步数是 3。

我的方法(速度不够快，无法通过)-

我从数组的第一个元素开始，并在距离 <=K 处标记所有与其相等的未标记元素并递增 steps 1.

Answer 1

首先考虑如何回答 K == N 的问题(即对子序列的长度没有任何有效限制)。您的答案应该是最小步数是数组中不同值的数量。

然后考虑当 K 减小时它是如何变化的；重要的是对于每个值 ，您需要覆盖选择集 {i: A[i] == n} 的 K 长度间隔的副本数>n 出现在 A 中。沿 A 走 K 长度间隔的朴素算法，在每个 A[i] 尚未覆盖 值的位置停止code>n 就足够了。