洛谷的 CF 的提交无了，所以可能没人来看了，但是在题解区是清一色的二分，而唯一一篇贪心题解的讨论还略显复杂的情况下，我还是希望提供一种比较简洁的贪心题解。
在复杂度允许的情况下，尽可能把东西丢给机子去做。 ——秋语橙
方便起见，以下记 \(MD=10^9\).
贪心做法需要一些结论，我这里直接给出来，前 2 个结论证明不再赘述，可参考 0htoAi 的题解。
-
两点间的最短路要么为 两点间直连的边长，要么为 两倍全局最小 \(a\) 的值；
-
图的直径必然可在相邻两点的最短路处取得；
-
最优策略必然将前 \(k-1\) 小的 \(a\) 赋值成 \(MD\)。
以下给出结论 3 的证明：
对于 \(k=1\) 的情况，显然成立。对于 \(k>1\) 的情况，根据结论 1，每一次赋值点的选取要么是当前全局最大 \(a\) 的相邻点（记为操作 1），要么为当前全局最小 \(a\)（记为操作 2）。注意到，一旦出现 2 个连续的 \(MD\)，我们就没有必要再执行操作 1 了，称为盈满状态。达到盈满状态后只需执行操作 2.无论怎样执行哪个操作，在第 \(k\) 次赋值之前，必然存在至少一个 \(a=MD\)，这时全局最大 \(a=MD\)，必然执行一次操作 1 后就达到了盈满状态，之后执行的操作 2 无非就是被提前了。
所以发现，在把前 \(k-1\) 小的 \(a\) 赋值成 \(MD\) 后，所有问题就被转化到 \(k=1\) 的问题上了。接下来考虑 \(k=1\) 的解法：
先约定一些变量：\(ans1\) 表示 \(\max\limits_{i=1}^{n-1}(\min(a_i,a_{i+1}))\)，\(ans2\) 表示全局最小 \(a\) 的两倍，\(ans3\) 表示全局非严格次小 \(a\) 的两倍。
当然你可以讨论，但是太麻烦了，而且极易出错。（我不知道有没有人用 \(O(1)\) 的讨论过了，如果有的话请与我交流一下，我先表示我的敬意Orz)
考虑一下前言中的那句话，发现现在甚至允许 \(O(n)\) 的复杂度。
所以不妨枚举每一个 \(a_i\)，尝试把 \(a_i\) 赋值成 \(MD\) 后更新答案，再把 \(a_i\) 变回来。
注意到赋值当前 \(a_i\) 时，无非就是变了 \(ans1\) 或是 \(ans2\)，接下来就这两种情况进行分别维护：
-
ans1:很暴力，因为改变 \(a_i\) 只会影响 \(\min(a_{i-1},a_i),\min(a_{i},a_{i+1})\)，所以重新算一下这两个值，和原来全局 \(ans1\) 取个 \(\max\)，作为当前的 \(ans1\)。
-
ans2:直接讨论，如果当前改变的是全局最小 \(a\)，那当前 \(ans2=ans3\)，否则不变。
把 \(ans1\) 和 \(ans2\) 取个 \(\min\) 就是当前改变 \(a_i\) 后的答案，更新 \(ans\) 即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long rd(){char ch=getchar();long long x=0,f=1;while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while('0'<=ch && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void wr(long long x){if(x<0){putchar('-');x=-x;}if(x>9) wr(x/10);putchar(x%10+'0');}
const long long N=1e5+10,MD=1000000000;
long long t,n,k,a[N+10],ans,ans1,ans2,ans3,mx,mx1,mx2;
struct node{long long w,id;}b[N+10];
bool cmp(node u,node v){return u.w<v.w;}
int main(){
long long i,j,u,v,x,y;
t=rd();
while(t--){
n=rd();k=rd();
for(i=1;i<=n;i++){
a[i]=rd();
b[i].w=a[i];b[i].id=i;
}
a[n+1]=0;//为下面(1)处理更简洁
sort(b+1,b+n+1,cmp);
for(i=1;i<k;i++) a[b[i].id]=MD;//把前k-1小的赋值成MD，转化为k=1问题
ans=0;ans1=0;
for(i=1;i<n;i++)//统计全局最大相邻更小a
ans1=max(ans1,min(a[i],a[i+1]));
ans2=MD;ans3=MD;
for(i=1;i<=n;i++){//统计2倍全局最小a和2倍全局次小a
if(a[i]<ans2){
ans3=ans2; ans2=a[i];
}
else if(a[i]<ans3) ans3=a[i];
}
ans2*=2;ans3*=2;
for(i=1;i<=n;i++){
u=a[i];a[i]=MD;
mx1=a[i-1];mx2=a[i+1];//改变相邻更小a的2种情况(1)
mx=max(ans1,max(mx1,mx2));
if(u*2==ans2) ans=max(ans,min(mx,ans3));//当前改的a等于全局最小a
else ans=max(ans,min(mx,ans2));//当前改的a不是全局最小a
a[i]=u;
}
wr(ans),putchar('\n');
}
return 0;
}