首先有一个比较明显的性质，直径最多经过两条边。
设全局最小值为 \(m\)。考虑从任意一点出发，经过全局最小值所在的点，然后再到任意点，花费是 \(2\times m\) 的。而任意边权 \(\geq m\)，走两条后的权值必定 \(\geq 2\times m\)。所以最多就是花费 \(2\times m\) 走两条边，不然只走一条。
那么 \(l,r\) 的最短距离就是 \(\min\left\{\min\limits_{l\le i\le r}a_i,2\times m\right\}\)。
显然考虑直径的话只要考虑相邻两个点就好了。
所以直径等于 \(\max\limits_{1\le i\lt n}\left\{\min\left\{a_i,a_{i+1},2\times m\right\}\right\}\)。
不难想到二分答案。
设当前正在 check 的值是 \(x\)，判断能否用不超过 \(k\) 次操作使得直径不小于 \(x\)。
对于 \(2\times a_i\lt x\) 的 \(i\)，先把它们变成 \(10^9\)。
现在只需使 \(\max\limits_{1\le i\lt n}\left\{\min\left\{a_i,a_{i+1}\right\}\right\}\) 不小于 \(x\) 就好了。
这些都很简单。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, inf = 1e9;
int T;
int n, k;
int a[N], b[N];
bool check(int x) {
for (int i = 1; i <= n; ++i) b[i] = a[i];
int res = 0;
for (int i = 1; i <= n; ++i) if (2 * b[i] < x) ++res, b[i] = inf;
bool flag = 0; for (int i = 1; i < n; ++i) if (min(b[i], b[i + 1]) >= x) flag = 1;
if (!flag) {
++res;
for (int i = 1; i <= n; ++i) if (b[i] >= x) flag = 1;
if (!flag) ++res;
}
return res <= k;
}
void solve() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int l = 1, r = 1e9;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}