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 38 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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;long long int a[2020];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=0; i
           
            a[i])mi=a[i]; } while(mi<=ma) { mid=(mi+ma)>>1; if(jug(mid)) { mi=mid+1; } else ma=mid-1; } // printf("%d\n",mid); if(jug(mid)) { while(jug(mid)) { mid++; } printf("%lld\n",mid-1); } else { while(!jug(mid)) { mid--; } printf("%lld\n",mid); } } return 0;}