二分答案

只能修改连续区间的人，考虑二分答案，也就是一个最大值x使得数组中的所有数值经过修改后都大于等于x，对于小于mid的值找到下标最小的开始连续修改，看最后剩下还有没有修改次数。

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
int a[N];

题目内容

小红有个$n$人组成的合唱团，第$i$个人的能力值为$a_i$。

现在将$n$个人排成一排，小红有$k$次训练的机会，让不超过$l$个连续的人能力人变为任意值。

如果合唱团的实力是所有人能力值的最小值。

你可以帮助小红求出合唱团的实力的最大值是多少吗?

输入描述

第一行三个整数$n，k，l，$表示人数，训练次数，每次训练的最大长度。$(2 <= n <= 10^5, 1 <= k * l < n)$

第二行$n$个整数$a_i$，表示第$i$个人的能力值为$a_i(1 <= a_i <= 1e9)$

输出描述

输出答案

样例1

输入

8 2 3
8 7 4 11 2 14 7 5

选择第3个人到第5个人和第6个到第8个人变成无穷大

输出

7

样例2

输入

8 2 2
4 7 4 11 2 14 7 5

输出

4

选择第5个人到第6个人和第7个到第8个人变成无穷大