B. Perfect Flush

Link: https://nanti.jisuanke.com/t/45345

Description

点击查看题面

You are given a list of integers and a number . It is guaranteed that each i from 1 to k appears in thelist at least once.Find the lexicographically smallest subsequence of x that contains each integer from 1 to k exactly once.

输入描述:

The first line will contain two integers and , with . The following n lines will each containan integer with .

输出描述:

Write out on one line, separated by spaces, the lexicographically smallest subsequence of x that has each integer from 1 to k exactly once

样例输入1
6 3
3
2
1
3
1
3
样例输出1
2 1 3
样例输入2
10 5
5
4
3
2
1
4
1
1
5
5
样例输出2
3 2 1 4 5

Probelm solving

这道题的意思是给我们个数，保证每个数都至少出现一次，让我们找到一个字典序最小的子序列包含的每个数且智能出现一次。
暴力肯定是不行的，这道题的题解做法是，首先统计每个数最后出现的一个位置。
然后遍历这个序列，我们称现在遍历到的这个序列的数为，做一下操作

  1. 如果还未出现在答案序列，并且答案序列不为空，就比较和答案序列中最后一个数的大小。如果大于序列中的最后一个数，直接放到答案序列就行，如果小于，就看后面还是否会出现当前答案序列的最后一个数，用当前的位置和答案序列中最后一个数出现的最后一个位置作比较即可。如果后面不会再出现了，也直接加到答案序列。
  2. 如果已经出现在答案序列，跳过。

最后输出即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
const int maxn = 2e5+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int d[4][2]={1,0,0,1,-1,0,0,-1};
int main() {
    ios::sync_with_stdio(0);
    #ifdef Uncle_drew
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #else
    #endif
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),ans,vis(n+1),pos(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i]])   continue;
        while(ans.size()>0&&a[i]<ans.back()&&i<pos[ans.back()]){
            vis[ans.back()]=0;
            ans.pop_back();
        }
        ans.pb(a[i]);
        vis[a[i]]=1;
    }
    for(auto i :ans){
        if(i!=ans.back())
            cout<<i<<" ";
        else
            cout<<i<<endl;
    }
    return 0;
}
赏