1984: LXX的能力值
Submit Page Summary Time Limit: 3 Sec Memory Limit: 128 Mb Submitted: 17 Solved: 6
Description
LXX学习了N种算法知识，并且对于不同的算法知识掌握的程度不一样。为了能够在比赛中取得更好的成绩，他需要把自己的弱项填补。 就像木桶一样，能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。已知LXX对第i种算法知识的能力值为Ai。LXX去向好心的上帝求救，上帝送给了他一个修补工具，但是最多只能使用M(M*L<N)次，且只能使连续的不超过L种知识的能力值提高至任意数值。现在问如何修补才能使能力值最小的最大呢？能力值的序列可以看成跟木桶类似的环状。
Input
第1行包含3个正整数，N, M, L。1≤N≤1000，1≤L≤20
第2行包含N个正整数，A1...Ai...An，1≤Ai≤1000000000
Output
每行输出结果。
Sample Input
8 2 3
8 1 9 2 3 4 7 5
Sample Output
7
Hint
我们要使最终能力值的最小值尽可能大，求这个最大的最小能力值。
这是一个环状木桶，最好的办法是，我们修补｛8,1,2｝和{4,5,6}这两组位置（即把他们的值提高到很大很大），还剩下两个数没被提升，第3个数9和第7个数7，最小值是7。
Source
2017年暑期集训校队选拔
Author
廖璇璇
题解：
二分能力值最大 的最小能力值
再遍历一次数组 检查可以达到这个最大的最小能力值不 就可以得到答案
队友问过我一个问题 ： 我二分的那个能力值 要是数组中没有那个值怎么办
其实这个是可以不用去管的 这么说 数组中没有m这个值但是有m+1，m+2
那么我们二分的时候 如果m可以得话 m+1肯定也是可以得
所以二分求出来的 一定会是数组中有的元素
#include <cstdio>
#include <time.h>
#include <cmath>
#include <stdlib.h>
#include <cstring>
using namespace std;
long long int a[];
long long int n,m,l;
bool zs(long long int y,long long int x)
{
long long int mm=m;
for(long long int i=; i<n; ++i)
{
if(a[y+i]<x)
{
mm--;
i=i+l-;
} }
if(mm<)return false;
return true;
}
bool jug(long long int x)
{
for(long long int i=; i<n; ++i)
{
if(zs(i,x))
return true;
}
return false;
}
int main()
{ while(~scanf("%lld%lld%lld",&n,&m,&l))
{
long long int ma=,mi=,mid;
for(long long int i=; i<n; ++i)
{
scanf("%lld",&a[i]);
a[n+i]=a[i];
if(ma<a[i])ma=a[i];
if(mi>a[i])mi=a[i];
}
while(mi<=ma)
{
mid=(mi+ma)>>;
if(jug(mid))
{
mi=mid+;
}
else
ma=mid-;
}
// printf("%d\n",mid); if(jug(mid))
{
while(jug(mid))
{
mid++;
}
printf("%lld\n",mid-);
}
else
{
while(!jug(mid))
{
mid--;
}
printf("%lld\n",mid);
} } return ;
}