Perfect Flush
题意数据范围思路代码
题意
给定
n
n
n和
k
k
k，并且给出长度为
n
n
n的数字序列，序列中的每个数字都不超过
k
k
k。求子序列中字典序最小的
k
k
k排列。
数据范围
1
≤
n
,
k
≤
200000
1 \leq n,k \leq 200000
1≤n,k≤200000
思路
用单调栈维护序列。首先开一个
l
a
s
t
last
last数组记录每一个数字出现了多少次，然后扫描序列，如果当前数字比栈顶元素小，并且栈顶元素在后面还会出现，那么弹出栈顶元素，再把当前数字压栈。最后输出栈中元素即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std
;
int nums
[200010], last
[200010], ans
[200010];
bool used
[200010];
stack
<int> st
;
int main()
{
int n
, k
;
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=n
;i
++){
int temp
;
scanf("%d",&temp
);
nums
[i
] = temp
;
last
[temp
] ++;
}
for(int i
=1;i
<=n
;i
++){
last
[nums
[i
]] --;
if(used
[nums
[i
]]) continue;
else{
while(!st
.empty()&&nums
[i
]<st
.top()&&last
[st
.top()]>0){
used
[st
.top()] = true;
st
.pop();
}
st
.push(nums
[i
]);
used
[nums
[i
]] = 1;
}
}
for(int i
=1;i
<=k
;i
++){
ans
[i
] = st
.top();
st
.pop();
}
for(int i
=k
;i
>1;i
--) printf("%d ", ans
[i
]);
printf("%d\n",ans
[1]);
return 0;
}
