D. Empty Graph #813 div2
Problem - D - Codeforces
题意是给你一组序列，编号1，2，3对应着点的编号，根据这个序列创建一个无向有权图。然后从点a到点b的权值就是对应在这个序列里面的[a,b]的最小值，然后找到所有从一个点到另外的一个点的最短路的权值最大。
可以有不超过k次的操作：选择一个任意索引，使得a[i]=x（x∈[1,1e9]）
贪心 二分都可以写
下面我说贪心的思路
这题你要从图里面发现很多性质才可以把这个题写掉
首先：图的最大权值必然是相邻的点的最小值，即min(a[i],a[i+1])
证明：点al到ar的权值为[l,r]的最小权值，你在一个数组里面有个值最小，因为有这个值的存在，包含这个点的所有区间对应到所有的点的权值都是那个最小的数，为了方便起见，这个值也就是相邻的点的权值，整体上来看最大的权值必然是某个相邻的点的权值
第二：这个题的本质是从a到b的最短路的最大值
a到b可以有两种走法：这里定义一个最小值ax（在x的位置上）
①：a->b，这种情况在区间[a,b]上面没有这个ax，也就是没有整体的这一个最小值。就是a直接到b，这个遍历一遍就好，取路上的最小权值然后取max
②：a->x->b，在这一段路径上包含了ax，也就是最小值在这个区间上面，那这个a到b的权值也就是先可以a到x，然后x到b，所以这种情况的权值就是ax*2
好，上面是两种可能的走法，如果k==0，那上面的就是答案了。
现在开始使用k，就开始依据上面然后基于贪心的思想，开始进行最小值的最大化
根据上面的第一种情况的表达式:maxn=max(maxn,min(a[i],a[i+1])
第二种情况是尽可能的把最小值变大，然后ax*2
一个是线性一个是平方，所以首选的是第二种：让最小值尽可能的变大
怎么变大？就是把前k-1小的数变成正无穷，然后第k个数理应就是变化后的最小值
刚刚说到前k-1小的数，把k-1次都留在操作最小值，然后第k次有两种选择：
要么是继续操作最小值，要么是增加a->b，这里操作一次，也就是增加一次即可（第一种操作），多了没意义，反正都是取两者的最小值。就是取两者种的最小值，无论怎么变化，我们都可以把其中一个权值变成无穷大，然后取最大权值的那个就好
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e9,mod=1e9+7;
int a[N],b[N];
signed main(){
//IOS;
int T;
//T=1;
cin>>T;
while(T--)
{
priority_queue<PAII,vector<PAII>,greater<PAII>> q;
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
q.push({a[i],i});
}
for(int i=1;i<=k-1;i++)//这里操作k-1次
{
auto t=q.top();
q.pop();
int pos=t.second;
q.push({INF,pos});
a[pos]=INF;
}
for(int i=1;i<=n;i++) b[i]=a[i];//b数组留最后一次操作过程量
auto t=q.top();
q.pop();
int p1=t.second;
q.push({INF,p1});
a[p1]=INF;//a数组继续操作最小值
int maxn=-1e18;
for(int i=1;i<=n-1;i++) maxn=max(maxn,min(a[i],a[i+1]));
sort(a+1,a+n+1);
int res1=min(a[1]*2,maxn);
sort(b+1,b+n+1);
int res2=min(b[1]*2,b[n]);
//这里b是把其中的一个变大，不管怎么样都是可以取到最大权值，所以这里不用具体实现增加过程量，直接是最大权值就好，也就是b[n]
cout<<max(res1,res2)<<"\n";
}
return 0;
}
/*
*/