CF1712D题解

这题有个显然的二分做法，可是我考场没想到，所以直接贪心的。虽然考场上没有 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。

然后分类讨论：

• 所有点都能染成 $10^9$，答案即为 $10^9$。
• 将前 $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$ 随着两点的距离单调不上升，两个点离得越远越不优。
• 第一种情况同 $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)));
    }
}