ABC299G 题解

Kevin090228 · 2023-04-22 22:05:28 · 个人记录

题意

给定一个长为 n 的序列 s，求它的所有子序列中，满足是一个长度为 m 的排列的，字典序最小的序列。

思路

字典序最小显然想到贪心，我们注意到在原来 s 中可能作为答案序列的第一个数的位置 i 满足是一段前缀（显然我们要保证 s_i 到 s_n 中 1 到 m 每种数各至少出现一遍，这个条件是单调的），贪心地，我们选择这个前缀中最小的 s_i 作为答案序列的第一个数，如果有多个相同的 s_i，选择更靠前的一个不会更劣。

选择答案序列的第二个数的过程与上面的类似。我们考虑用双指针维护此时当前能选的 s_i 的位置区间，具体地，我们维护最靠右的使 s_r 到 s_n 中所有答案序列中未出现过的字符都至少出现一次的 r，令答案序列的上一个数在序列 s 中对应的下标为 l，则我们这一次就在区间 (l,r] 中贪心选择，在双指针的同时维护一个优先队列即可。

时间复杂度 O(n\log n)。

代码

int a[200200];
int cnt[200200],cc;
bool flag[200200];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=n;i++)
    {
        cnt[a[i]]++;
        if(cnt[a[i]]==1) cc++;
    }
    set<pii> st;
    int p=1;
    st.insert(mp(a[1],1));
    int lst=0;
    for(int i=m;i>=1;i--)
    {
        while(p<=n&&(flag[a[p]]||cnt[a[p]]>1))
        {
            cnt[a[p]]--;
            p++;
            st.insert(mp(a[p],p));
        }
        while(sz(st)&&(flag[st.begin()->first]||st.begin()->second<=lst))
            st.erase(st.begin());
        printf("%d ",st.begin()->first);
        lst=st.begin()->second;
        flag[st.begin()->first]=1;
    }
    return 0;
}