二分

首先有一个比较明显的性质，直径最多经过两条边。

设全局最小值为 $m$。考虑从任意一点 $u$ 出发，经过全局最小值所在的点，然后再到任意点，花费是 $2\times m$ 的。而任意边权 $\geq m$，走两条后的权值必定 $\geq 2\times m$。所以最多就是花费 $2\times m$ 走两条边，不然只走一条。

然后考虑 $l,r$ 相距越远，它们之间的那条边越小，所以考虑最远点的时候只需考虑相邻两点就行了。

而相邻两点 $i-1,i$ 的最短距离为 $\min{a_{i-1},a_{i},2\times m}$。

所以直径 $D=\max\limits_{i\in[2,n]}{\min{a_{i-1},a_{i},2\times m}}$。

考虑这是一个最大值套最小值这种形式，上二分答案。

设当前判断使用 $\leq k$ 次操作是否能使答案为 $mid$。

首先如果 $2\times m<mid$,那么无论如何都可以通过全局最小走到任意点，所以先把 $2\times a_i< mid$ 的位置全部置为 $10^9$。

然后现在只需考虑 $\max\limits_{i\in [2,n]} {\min{a_{i-1},a_i}}$ 了。

发现只需要有一个 $\min{a_{i-1},a_{i}}\geq mid$ 即可。

所以如果已经满足无需操作，否则如果存在 $a_i\geq mid$，改掉与他相邻的其中一个即可，否则需要改两个。

判一下操作次数是否 $\leq k$ 返回即可。

复杂度 $O(n\log W)$，$W$ 是值域。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
#define grep(b,c) for(int c(head[b]);c;c=nxt[c])
#define Clear(a,n) memset(a,0,((n)+3)*sizeof(a[0]))
typedef long long LL;
typedef std::pair<int,int> pii;
using namespace std;
inline int read()
{
	int res=0;char ch=getchar();bool flag=0;while(ch<'0'||ch>'9')flag^=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return flag ? -res : res ;
}
inline void rd(bool &x){char c;do c=getchar();while(c!='0'&&c!='1');x=c=='1';}
inline void print(LL x){if(x>9)print(x/10);putchar(x%10+'0');}
//template<typename T> inline T min(const T&x,const T&y){return x<y?x:y;}
//template<typename T> inline T max(const T&x,const T&y){return x<y?y:x;}
template<typename T> inline T Swap(T&x,T&y){T tmp=x;x=y;y=tmp;}
template<typename T> inline T Abs(T&x){return x<0?-x:x;}
const int N=1e5+10,INF=1e9;int a[N],n,K,A[N];
inline bool check(int lm)
{
	
	memcpy(A,a,(n+3)*sizeof(int));
	int cc=0;rep(1,n,i){if(2*A[i]<lm)++cc,A[i]=INF;}
	bool f1=0,f2=0;rep(2,n,i)if(min(A[i],A[i-1])>=lm){f1=1;break;}
	rep(1,n,i)if(A[i]>=lm){f2=1;break;}
	if(!f1)++cc;if(!f2)++cc;
	return cc<=K;
}
inline void Solve()
{
	n=read();K=read();rep(1,n,i)a[i]=read();
	int l=1,r=1e9,res=1e9,mid;
	while(l<=r)check(mid=(l+r)>>1)?l=mid+1,res=mid:r=mid-1;
	printf("%d\n",res);
}

signed main()
{
	int T=read();
	while(T--)Solve();
	return 0;
}