两个整数N<=10^5和K<=N给出,其中N是数组的大小A[],并K是连续序列,我们可以在我们的process.Each元素选择的长度A[i]<=10^9。现在假设数组的所有元素都是未标记的。在每个步骤中,我们将选择长度的任何子序列,K如果该子序列具有未标记的元素,则将标记所有在序列上最小的未标记的元素。现在如何计算标记所有元素的最小步骤数?
N<=10^5
K<=N
N
A[]
K
A[i]<=10^9
为了更好地理解问题,请参见以下示例-
N=5 K=3 A[]=40 30 40 30 40
N=5 K=3
A[]=40 30 40 30 40
步骤1-选择间隔[1,3]并标记A [1]和A [3]
步骤2-选择间隔[0,2]并标记A [0]和A [2]
步骤3-选择间隔[2,4]并标记A [4]
因此,此处的最小步骤数为3。
我的方法(不够快无法通过)
我从数组的第一个元素开始,并在距离上标记所有与之相等的未标记元素,<=K并递增steps1。
<=K
steps
首先考虑您将如何回答K== 的问题N(即对子序列的长度没有任何有效限制)。您的答案应该是最小步骤数是数组中不同值的数目。
然后考虑这种变化如何K减少;重要的是,K您需要覆盖多少个长度间隔的副本才能覆盖中存在的{i: A[i] == n}每个值的选择集。天真的算法是沿,沿一个长度间隔行走,在尚未覆盖该值的每个位置处停止,这是完全足够的。n``A``K``A``A[i]``n
{i: A[i] == n}
n``A``K``A``A[i]``n