CF1712D题解
0htoAi
2022-08-15 20:21:51
这题有个显然的二分做法，可是我考场没想到，所以直接贪心的。虽然考场上没有 AC，但是做法跟补题的时候的做法也差不多。
考虑原图中任意两个点 $(l,r)$，$1 \leq l < r \leq n$，它们之间的最短路只有可能是这两种情况之一：
* 从 $l$ 直接走到 $r$，长度为 $\min_{i=l}^{r}(a_i)$。
* 从 $l$ 走到全局最小点 $a_{\min}$，再从 $a_{\min}$ 走到 $r$，长度为 $2a_{\min}$。
其实可能出现 $a_{\min}=\min_{i=l}^{r}(a_i)$ 的情况，不过由于最短路是以上两种情况取较小值，所以可以忽略这个问题。
首先明确只要改变一个点的值，一定把其改成最大值，即 $10^9$。
然后分类讨论：
* $k=n$ 时：
所有点都能染成 $10^9$，答案即为 $10^9$。
* $n>k>1$ 时：
将前 $k-1$ 小的点变成 $10^9$，此时对于任何一个点到其相邻点，把小的一个变成 $10^9$，由于前面至少将 $1$ 个点变成过 $10^9$，所以一定能找到这个 $10^9$，把其相邻点也变成 $10^9$。设第 $k$ 小的点为 $a_k$，则此时最长的两点最短路长度就为 $\min(10^9,2a_k)$。
即可以得出结论：当 $k>1$ 时，答案不会小于 $\min(10^9,2a_k)$。
然后考虑常规情况，根据最上面的，最短路只有可能是 $2$ 种情况之一，于是模拟。要使得全局最小点尽可能大，于是把前 $k$ 小的 $a$ 都变成 $10^9$，然后对于一对相邻的点 $(i,i+1)$，其最短路长度为 $\min(a_i,a_{i+1})$。找出最大的这个值，即找出 $\max_{i=1}^{n-1}(\min(a_i,a_{i+1}))$。综上可得全局最长的最短路为 $\max(\min(10^9,2a_k),\min(\max_{i=1}^{n-1}(\min(a_i,a_{i+1})),2a_{k+1}))$。其中 $a_k$ 和 $a_{k+1}$ 表示第 $k$ 和第 $k+1$ 小的 $a$，而 $a_i$ 表示原数组 $a$ 的第 $i$ 个值。
为什么要选相邻的点？因为两点中间的 $\min$ 随着两点的距离单调不上升，两个点离得越远越不优。
* $k=1$ 时：
第一种情况同 $n>k>1$ 时的第一段。但是由于 $k=1$，所以不保证找得到 $10^9$，找 $a_{\max}$ 就行了。即答案不会小于 $\min(a_{\max},2a_{\min})$。
第二种情况同 $n>k>1$ 时的“常规情况”。
则此时全局最长最短路为 $\max(\min(a_{\max},2a_{\min}),\min(\max_{i=1}^{n-1}(\min(a_i,a_{i+1})),2a_2))$。其中 $a_{\min}$ 表示 $a$ 的最小值， $a_2$ 表示 $a$ 的次小值，$a_{\max}$ 表示 $a$ 的最大值。注意 $\min(a_i,a_{i+1})$ 里的这个 $a$ 是把 $a_{\min}$ 变成 $10^9$ 之后来找的， $1<k<n$ 时同样也是先赋值再算。
如果题解看糊涂了可以看代码：
```
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+50;
int N,K;
struct Dot
{
int Val,id;
}d[MAXN];
bool cmp(Dot a,Dot b)
{
return a.Val<b.Val;
}
int a[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&K);
for(int i=1;i<=N;i++)
{
scanf("%d",&d[i].Val);
d[i].id=i;
a[i]=d[i].Val;
}
if(K==N)
{
puts("1000000000");
continue;
}
sort(d+1,d+N+1,cmp);
int ans1,ans2,ans3,ans4;
if(K==1)
{
ans1=d[1].Val*2;
ans2=0;
for(int i=1;i<=N;i++)
{
ans2=max(ans2,a[i]);
}
ans3=d[2].Val*2,ans4=0;
a[d[1].id]=1000000000;
for(int i=1;i<N;i++)
{
ans4=max(ans4,min(a[i],a[i+1]));
}
printf("%d\n",max(min(ans1,ans2),min(ans3,ans4)));
continue;
}
ans1=min(1000000000,d[K+1].Val*2),ans2=0;
for(int i=1;i<=K;i++)
{
a[d[i].id]=1000000000;
}
for(int i=1;i<N;i++)
{
ans2=max(ans2,min(a[i],a[i+1]));
}
ans1=min(ans1,ans2);
printf("%d\n",max(min(1000000000,d[K].Val*2),min(ans1,ans2)));
}
}
```