给出了两个整数N<=10^5和K<=N，其中N是数组的大小，A[]是K我们可以在流程中选择的连续子序列的长度。每个元素A[i]<=10^9。现在假设最初数组的所有元素都没有标记。在每一步中，我们将选择任何长度的子序列K，如果该子序列具有未标记的元素，那么我们将标记所有序列中最小的未标记元素。现在如何计算标记所有元素的最小步骤数？
为了更好地理解问题，请参见这个例子——
N=5 K=3
A[]=40 30 40 30 40
步骤 1- 选择区间 [1,3] 并标记 A[1] 和 A[3]
Step2- 选择区间 [0,2] 并标记 A[0] 和 A[2]
步骤 3- 选择区间 [2,4] 并标记 A[4]
因此这里的最小步数是 3。
我的方法（速度不够快，无法通过）-
我从数组的第一个元素开始，将所有未标记的元素标记为在距离处等于它<=K并递增steps1。
First consider how you'd answer the question for K == N (i.e. without any effective restriction on the length of subsequences). Your answer should be that the minimum number of steps is the number of distinct values in the array.
Then consider how this changes as K decreases; all that matters is how many copies of a K-length interval you need to cover the selection set {i: A[i] == n} for each value n present in A. The naive algorithm of walking a K-length interval along A, halting at each position A[i] not yet covered for that value of n is perfectly adequate.
正如我们所见，最小步数 = N/k 或 N/k+1，最大步数 =(n+k-1)。我们必须优化步骤总数，这取决于我们过去所做的选择历史，即动态解决方案。
可以在 O(n) 中解决如下：跟踪每个元素 a[i]。如果之前没有跟踪 a[i]，则映射数字及其索引并增加计数器。如果之前跟踪了数字，则检查其 (last index-curr_index)>=K 是否更新索引并增加计数。打印计数。Map STL 将是有益的。