C. k-Amazing Numbers

我的思路和标程不太一样,用了排序和二分,复杂度大一些,O(n*logn)。

统计相同两个数的距离,对于出现的每个数x,记录能覆盖所有x所需要的最小区间长度,记为len[x]。将len[x]与x捆绑到结构体里,用len[x]大小排序,之后用mi[i]记录1~i 的最小x(前缀中最小的x)。最后在输出答案的时候,如果长度 i 小于min{len[x]},则输出-1,否则二分查找小于等于 i 的最大位置k,输出前缀最小x即mi[k]。

以上是个人思路,说的比较绕,大家可以去看看官方题解的O(n)做法。

Codeforces Round #673 Editorial

在这里插入图片描述

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10,inf=0x3f3f3f3f;
int n,a[N],last[N],len[N],t[N],ans[N],mi[N];
struct node
{
    int len,x;
}p[N];
bool cmp(node s1,node s2)
{
    return s1.len<s2.len;
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(last,-1,sizeof(last));
        memset(len,inf,sizeof(inf));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int x=a[i];
            if(last[x]==-1) // a[i]第一次出现
            {
                len[x]=i; // 覆盖所有x所需的长度
                last[x]=i; // 更新位置
            }
            else
            {
                len[x]=max(len[x],i-last[x]); // 更新覆盖所有x所需的长度
                last[x]=i; // 更新位置
            }
        }
        int cnt=0;
        int low=inf;
        for(int i=1;i<=n;i++)
        {
            if(last[i]!=-1) // 出现过,记录最后一次出现位置
            {
                len[i]=max(len[i],n+1-last[i]);
                p[++cnt].len=len[i];
                p[cnt].x=i;
                low=min(low,len[i]); // 下界,最短长度
            }
        }
        sort(p+1,p+cnt+1,cmp);

        mi[0]=inf;
        for(int i=1;i<=cnt;i++)
        {
            mi[i]=min(mi[i-1],p[i].x);
            t[i]=p[i].len; // 拷贝
        }
        for(int i=1;i<=n;i++) // 长度为i
        {
            if(i<low)ans[i]=-1;
            else
            {
                int k=upper_bound(t+1,t+cnt+1,i)-t-1; // <=i的数,下标
                ans[i]=mi[k];
            }
        }
        for(int i=1;i<=n;i++)
            i==n?printf("%d\n",ans[i]):printf("%d ",ans[i]);
    }
    return 0;
}
/*
100
10
1 2 3 1 3 2 1 2 3 1
*/