hiho 修补木桶(二分)

2018年03月14日 9点热度 0人点赞 0条评论
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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

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

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

已知修补工具一共可以使用M次(M*L

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

输入

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

第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)。

#include
#include
#include
#include
using namespace std;
int n,m,l,a[2*1005],b[1005],rr,ll,mid;
bool is_ok() {
	if(b[0]==mid) return true;
	//时间复杂度为n*n,那个l*n的也ac了,但是我没证明。。。 
	bool f1=false;
	for(int i=0; i());
	ll=0,rr=n-1;
	while(ll
#include
#include
#include
#include
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=l) break;
	}
	return f1;
}
int main() {
	scanf("%d%d%d",&n,&m,&l);
	for(int i=0; i());
	ll=0,rr=n-1;
	while(ll

未经允许不得转载!hiho 修补木桶(二分)

update

纸上得来终觉浅, 绝知此事须躬行。