Go语言视频零基础入门到精通

admin

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

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

已知一个木桶的桶壁由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 38 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)。

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;int n,m,l,a[2*1005],b[1005],rr,ll,mid;bool is_ok() {        if(b[0]==mid) return true;        //时间复杂度为l*n        int cnt=0;//需要的段数        int cnt_start=0;//已开始的起点数        bool f1=false;        for(int i=0; i<n; ++i) {                int cnt=1,j,last;                if(a<mid) {                        last=i+n;                        j=i+l;                        ++cnt_start;                } else continue;                while(j<last) {                        if(a[j]<mid) {                                ++cnt;                                j+=l;                        } else ++j;                }                if(cnt<=m) {                        f1=true;                        break;                }                if(cnt_start>=l) break;        }        return f1;}int main() {        scanf("%d%d%d",&n,&m,&l);        for(int i=0; i<n; ++i)                scanf("%d",a+i);        memcpy(b,a,n*sizeof(int));        memcpy(a+n,a,n*sizeof(int));        sort(b,b+n,less<int>());        ll=0,rr=n-1;        while(ll<rr) {                int t=(ll+rr+1)/2;//这个+1要注意                mid=b[t];                if(is_ok()) {                        ll=t;                } else {                        rr=t-1;//这个地方要注意下                }        }        cout<<b[ll]<<endl;        return 0;}