《修补木桶》题目分析

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

我们考虑这样一个问题，假设最终最短的木板长度至少是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)。