小编典典

关于如何根据给定条件找到最小步数来标记给定数组的所有元素的任何提示?

algorithm

两个整数N<=10^5K<=N给出,其中N是数组的大小A[],并K是连续序列,我们可以在我们的process.Each元素选择的长度A[i]<=10^9。现在假设数组的所有元素都是未标记的。在每个步骤中,我们将选择长度的任何子序列,K如果该子序列具有未标记的元素,则将标记所有在序列上最小的未标记的元素。现在如何计算标记所有元素的最小步骤数?

为了更好地理解问题,请参见以下示例-

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。


阅读 376

收藏
2020-07-28

共1个答案

小编典典

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

然后考虑这种变化如何K减少;重要的是,K您需要覆盖多少个长度间隔的副本才能覆盖中存在的{i: A[i] == n}每个值的选择集。天真的算法是沿,沿一个长度间隔行走,在尚未覆盖该值的每个位置处停止,这是完全足够的。n``A``K``A``A[i]``n

2020-07-28