hihocoder #1362 : 修补木桶（二分）

本文主要是介绍hihocoder #1362 : 修补木桶（二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

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

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

二分最小的高度值

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 1010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int a[MAXN];
int n,m,l;int times(int b)
{int mi=1010;for(int i=0;i<n;i++)//枚举起点位置{int num=0;for(int j=0;j<n;j++)//枚举与起点的距离{int k=(i+j)%n;if(a[k]<b){num++;j+=(l-1);}}mi=min(mi,num);}return mi;
}int main()
{//fread;while(scanf("%d%d%d",&n,&m,&l)!=EOF){int mx=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);mx=max(mx,a[i]);}int left,right,mid;left=0; right=mx+1;while(left<=right){mid=(left+right)/2;int num=times(mid);if(num<=m)left=mid+1;else right=mid-1;}printf("%d\n",right);}return 0;
}

 

这篇关于hihocoder #1362 : 修补木桶（二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---