CF1848B Vika and the Bridge

LimpidSlirm · 2023-10-30 19:42:25 · 题解

题意

给定一个序列，从 0 号点开始往后跳，每次只能跳到与前一个点颜色相同的点，有一次改变颜色的机会，求路径上最长的一次跳跃的距离的最小值。

Solution

赛时一眼二分，然后写着写着发现根本没必要二分，因为只有一次改变颜色的机会。

贪心地去求答案，对于每一种颜色记录两个点之间的距离的最大值和次大值，然后把最大值的那段区间的中点颜色更改成当前颜色。令最大值为 max，次大值为 sec。则 \min(\lfloor \dfrac{max}{2} \rfloor,sec) 即为最优解。

记得处理到终点即第 n+1 号点的距离。

时间复杂度为 \mathcal{O}(n)。

code

#include<bits/stdc++.h>
inline int read()
{
    long long res=0,flag=1;
    char ch=getchar();
    while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=getchar();
    while(isalnum(ch)) res=res*10+ch-'0',ch=getchar();
    return res*flag;
}
int val[200010];
int ans[200010][3];
void solve()
{
    int n=read(),k=read(),res=0x3f3f3f3f;
    memset(ans,0,sizeof ans);
    for(int i=1;i<=n;i++)
        val[i]=read();
    for(int i=1;i<=n;i++)
    {
        if(i-ans[val[i]][0]>=ans[val[i]][1])
            std::swap(ans[val[i]][1],ans[val[i]][2]),ans[val[i]][1]=i-ans[val[i]][0];
        else if(i-ans[val[i]][0]>=ans[val[i]][2])
            ans[val[i]][2]=i-ans[val[i]][0];
        ans[val[i]][0]=i;
    }
    for(int i=1;i<=k;i++)
    {
        if(n+1-ans[i][0]>=ans[i][1])
            std::swap(ans[i][1],ans[i][2]),ans[i][1]=n+1-ans[i][0];
        else if(n+1-ans[i][0]>=ans[i][2])
            ans[i][2]=n+1-ans[i][0];
        ans[i][1]--,ans[i][2]--;
    //  std::cout<<i<<" "<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<std::endl;
        res=std::min(res,std::max((int)(ans[i][1]/2),ans[i][2]));
    }
    printf("%d\n",res);
    return ;
}
int main(int argc,const char *argv[])
{
    int T=read();
    while(T--)
        solve();
    return 0;
}