如何任何提示，根据给定的条件下发现的步骤，以纪念给数组中的所有元素最低数量？ [英] Any hint on how to find minimum number of steps to mark all element of given array according to given conditions?
问题描述
两个整数 N'LT = 10 ^ 5 和 K＆LT; = N 给出，其中<$ C $ ç> N 是数组的大小 A [] 和 K 是长度连续的子序列，我们可以在我们的process.Each元素选择 A [1] - = 10 ^ 9 。现在假设数组的最初所有的元素都没有标记。在每个步骤中，我们将选择长度 K 的任意子，如果这个序列有无人盯防的元素，然后我们将标记所有未标记的元素这是最小susequence。现在，如何计算步数最少，以纪念所有元素？
Two integers N<=10^5 and K<=N are given, where N is the size of array A[] and K is the length of continuous subsequence we can choose in our process.Each element A[i]<=10^9. Now suppose initially all the elements of array are unmarked. In each step we'll choose any subsequence of length K and if this subsequence has unmarked elements then we will mark all the unmarked elements which are minimum in susequence. Now how to calculate minimum number of steps to mark all the elements?
为了更好地理解问题，看到这个example--
For better understanding of problem see this example--
N = 5，K = 3
A [] = 40 30 40 30 40
步骤1-选择区间[1,3]和标记[1]和A [3]
Step 1- Select interval [1,3] and mark A[1] and A[3]
Step2-选择区间[0,2]，并标明A [0]和A [2]
Step2- Select interval [0,2] and mark A[0] and A[2]
步骤3选择区间[2,4]和标记[4]
Step 3- Select interval [2,4] and mark A[4]
这里步骤因此最小数目是3
Hence minimum number of steps here is 3.
我的做法（这是不够快，无法通过） -
我从数组的第一个元素开始，并标志着人人平等无人盯防的元素，它在距离＆LT; = K 和增量步骤 1。
I am starting from first element of array and marking all the unmarked elements equal to it at distance <=K and incrementing steps by 1.
推荐答案
首先考虑你如何回答的 K == n中的问题（即没有在子序列的长度任何有效的限制）。你的答案应该是，步骤的最小数目是不同值的阵列中的数
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.
然后考虑如何更改为 K 减小;所有重要的是一个 K - 长度间隔的多个副本如何，你需要支付的选择集 {我：A [1] == N} 为每个值 N present在 A 。走了 K - 长度区间下沿 A ，停止在每个位置的天真算法 A [我] 尚未覆盖的的那个值 N 是完全足够了。
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.
这篇关于如何任何提示，根据给定的条件下发现的步骤，以纪念给数组中的所有元素最低数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
