hiho一下第193周《修补木桶》题目分析

1
0

《修补木桶》题目分析

本题可以使用二分答案的思路解决。

我们考虑这样一个问题,假设最终最短的木板长度至少是K,最小需要使用修复工具几次? 为了描述方便我们将这个最少次数记作F(K)。

于是我们的问题变成求出最大的K,满足F(K) <= M。

如果我们将F(K)看成一个函数,随着K增加,我们要修复的木板越来越多,显然F(K)也会越来越大。

换句话说F(K)是单调递增的。我们可以用二分来求出最大的K。

考虑 1 <= Ai <= 100000000,答案也一定在[1, 100000000]之间。在这个范围内二分的复杂度是O(log(Max{Ai}))。

然后我们的问题是对于确定的K,计算F(K)。

当K确定是,我们就可以确定哪些木板需要被修复(Ai < K的木板)。

由于木桶是环形的,我们需要枚举起点,复杂度O(N)。

一旦起点确定,就可以贪心求出每一次修复的位置。从而计算出F(K),复杂度O(N)。

于是总复杂度是O(log(Max{Ai})N^2)

这个算法可以通过所有的数据。

不过上面算法中二分和计算F(K)都有优化的空间。

对于二分答案这部分,实际上答案一定是某个Ai,所以我们可以优化到O(logN)的二分。

对于计算F(K)的部分,考虑到修复范围是L,所以O(N)的枚举起点可以优化到O(L)。

  • 各位大佬,对于计算F(K)的部分,考虑到修复范围是L,所以O(N)的枚举起点可以优化到O(L)。这个怎么分析,想不通,求解。。。

  • 添加评论
  • reply

2 answer(s)

2

各位大佬,对于计算F(K)的部分,考虑到修复范围是L,所以O(N)的枚举起点可以优化到O(L)。这个怎么分析,想不通,求解。。。

  • 随便找一块要修复的木板,这块木板一定要被某个L覆盖。模板和L的相对位置有L种可能;一旦相对位置确定,后面就可以贪心了。

  • 确定L个相对位置,虽然ac了,但是后面的有些为起点的不一定全都覆盖到了,我怀疑是不是数据太水了。。

  • 添加评论
  • reply
0

这个暴力模拟不是O(n^2)的吗...

  • 后面有一句“总复杂度是”,O(N) 只是说模拟起点这个外循环的复杂度

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享