二分查找——修补木桶

修补木桶 - 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;
}