二分查找——修补木桶
修补木桶 - HihoCoder 1362 - Virtual Judge (vjudge.net)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
#define QAQ 0
const int N=2e5+5,inf=0x3f3f3f3f,mod=1e7+7;
int a[100006],n,m,l;
bool check(int val){
int cnt = 0;
for(int i=1;i<=n;i++)
{
cnt = 0;
for(int j=1;j<=n;j++)
{
if(a[(i+j)%n]<val)
{
j +=(l-1);
cnt++;
}
}
if(cnt<=m)
{
return true;
}
}
return false;
}
void solve()
{
cin>>n>>m>>l;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int l = 0,r = 100006,ans = 0 ;
while(l<=r){
int mid = l+r+1>>1;
if(check(mid))
{
ans= mid;
l = mid+1;
}
else{
r = mid -1 ;
}
}
cout<<ans<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
//cin>>T；
while(T--)
{
solve();
}
return QAQ;
}