题面
大秦为你打开题目传送门
题目描述
有一个长 $N$ 的序列，保证其中包含 $1$ ～ $M$ ，请你找到一个长 $M$ 的子序列，使得其中每个数字都出现了一次，并使得排列的字典序最小。
思路
首先题目保证有解。我们考虑一下，我们可以从两个角度看问题，一是选择数字，二是删除数字。我们看这道题的考虑方向，我们要让字典序尽可能小，其实就是一些前面的大元素换到后面的替换过程，或者说更像插入和删除。这是候我们就不难想到，题目让我们求的序列，可以是原序列入栈出栈循环得到的产物。我们考虑如何去做这个栈。如果当前的这个树子比栈顶要小，那么把它替换过来坑定更优，但是在把栈顶删除的同时还要考虑能不能把它换回来，所以我们还要考虑后面还有多少种这个数字。基本思路就是这样，我们看代码：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
typedef pair<int, int> pii;
typedef unsigned long long ull;
namespace FastIO {
template <typename T>
inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar()))
if (ch == '-')
f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... x_) {
read(x);
read(x_...);
return;
}
};
using namespace FastIO;
const int N = 1e6 + 10;
int n, m;
int a[N];
int cnt[N];
int stk[N], tp;
bool instk[N];
inline void Input() {
read(n, m);
for (int i = 1; i <= n; i++) {
read(a[i]);
cnt[a[i]]++;
}
}
inline void Work() {
for(int i = 1; i <= m; i++) instk[i] = 0;
tp = 0;
for (int i = 1; i <= n; i++) {
cnt[a[i]]--;
if (instk[a[i]])
continue;
while (stk[tp] > a[i] && cnt[stk[tp]] != 0) {
instk[stk[tp--]] = 0;
}
stk[++tp] = a[i];
instk[a[i]] = 1;
}
for (int i = 1; i <= m; i++) {
printf("%d ", stk[i]);
}
printf("\n");
}
int main() {
int T = 1;
read(T);
while (T--) {
Input();
Work();
}
return 0;
}
|
