找到滚动所能覆盖的最小块数，以便修复所有损坏的块？

Question

一条分成"_ **__*___“的道路，其中”*“代表损坏的街区。有一个用来修路的压路机。Rollar具有固定长度K。给定损坏位置(N)和rollar K的大小，找出rollar可以覆盖的最小块数，以便修复所有损坏的块。Rolar可能不会持续维修。可能会有差距。you can read it here.

Answer 1

假设损坏的位置是pos，pos1，...，posn-1。创建dp数组。这里，dpidx表示滚轮为修复从索引idx到n-1的损坏而覆盖的最小块数，它从索引idx开始。现在，dpn-1=k；对于任何其他指数，假设i，让我们计算dpi:如果辊保持在posi，那么辊将覆盖到posi+k。假设posi+k之后的损坏位置在索引j。现在，有两种可能的情况。1.滚轮向上滚动到覆盖索引j的位置。ans1=dpj+1+( ans2=dpj+k -posi) 2.滚轮在索引j处再次开始。然后，dpi=min(ans1，ans2)索引搜索可以使用二进制搜索来完成。因此，总体时间复杂度: O(n*log(n))。