描述

一只木桶能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。

已知一个木桶的桶壁由N块木板组成，第i块木板的长度为Ai。

现在小Hi有一个快捷修补工具，每次可以使用修补工具将连续的不超过L块木板提高至任意高度。

已知修补工具一共可以使用M次(M*L<N)，如何修补才能使最短的那块木板最高呢？

注意: 木板是环形排列的，第N-1块、第N块和第1块也被视为连续的。

输入

第1行：3个正整数，N, M, L。分别表示木板数量，修补工具使用次数，修补工具每次可以同时修补的木板数。 1≤N≤1,000，1≤L≤20，M*L<N

第2行：N个正整数，依次表示每一块木板的高度Ai，1≤Ai≤100,000,000

输出

第1行：1个整数。表示使用修补工具后，最短木块的所能达到的最高高度

样例说明

第一个修补工具覆盖[2 3 4]

第二个修补工具覆盖[5 8 1]

样例输入

8 2 3
8 1 9 2 3 4 7 5

样例输出

7

官方分析

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

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

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int N, M, L, A[1005], LEFT = INT_MAX, RIGHT = INT_MIN;
bool Check(int mid)
{
    for(int i = 0; i < N; i++) { //枚举起点
        int times = 0; //修补次数
        for(int j = i; j < i + N; j++) { //遍历一圈木桶计算当前mid需要几次修补次数
            if(A[j % N] < mid) {
                times++;
                j = j + L - 1; //因为小于mid，所以必须修补，则L范围都修补，-1是因为for要+1
            }
        }
        if(times <= M) return true;
    }
    return false;
}

int main()
{
    cin >> N >> M >> L;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        LEFT = min(LEFT, A[i]);
        RIGHT = max(RIGHT, A[i]);
    }
    while(LEFT <= RIGHT) {
        int mid = (LEFT + RIGHT) / 2;
        if(Check(mid)) LEFT = mid + 1;
        else RIGHT = mid - 1;
    }
    cout << RIGHT << endl;
    return 0;
}

整体来说就是枚举起点，然后一次又一次遍历遍历。