题目描述
https://codeforces.com/contest/1435/problem/D
维护一个小根堆，每次有两种操作
向堆中加入一个数和取出堆顶 $x$
要求还原加数的序列
Solution
对于已经在堆里的元素来说，如果此时取出堆顶元素 $x$，说明堆内的元素都大于 $x$
换句话来说，越晚加入的元素的限制越弱
如果按照加入的顺序的话，我们大概能得到下面这种限制
且 $x_i$ 一定单调递减，假设我们现在要取出 $x$，那么贪心的进行选择一定要取出从左到右第一个小于 $x$ 的具有限制 $x_i$ 的那一段中的某一个
但是这样就相当于将这段以及后面段的限制都变成大于 $x$，那么就相当于取出最后面那段，我们发现这个东西符合先进后出，其实就是一个栈
所以我们模拟一下就好
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
| #include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#define maxn 100010
#define ll long long
#define pb push_back
#define cn const node
#define cQ const Queue
#define gc getchar
#define INF 1000000000
using namespace std;
int read() {
int x = 0; char c = gc();
while (!isdigit(c)) c = gc();
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
return x;
}
int n, a[maxn * 2];
char s[10];
struct node {
int k, v;
node() {}
node(int _k, int _v) { k = _k; v = _v; }
}; stack<node> S; int c1;
int ans[maxn];
int main() {
cin >> n;
for (int i = 1; i <= 2 * n; ++i) {
scanf("%s", s + 1);
if (s[1] == '+') a[i] = 0;
else scanf("%d", &a[i]);
}
for (int i = 1; i <= 2 * n; ++i)
if (!a[i]) S.push(node(++c1, 0));
else {
if (S.empty() || S.top().v > a[i]) return puts("NO"), 0;
ans[S.top().k] = a[i]; S.pop();
if (!S.empty() && S.top().v < a[i]) S.top().v = a[i];
}
puts("YES");
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}
|
但是总感觉这样分析一道 $div2$ 的 $C$ 题有点过分了
所以我们换一个做法，我们这次考虑反着做
我们将取出堆顶 $x$ 视为加入数 $x$
加入一个数，我们视为取出一个数
我们发现连续一串加入的数 $x$ 一定是递减的
我们贪心的思考发现为了尽可能序列合法，我们一定在取出数时取出最小的数
因为这样可以尽可能的让下次加入的数做到递减（因为下次加入的数是固定的
因为加入的数是递减的，每次取出的时候又一定取最小的，所以这还是一个先进后出，所以还是一个栈（我tm
所以我们模拟一下即可
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
| #include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#define maxn 100010
#define ll long long
#define pb push_back
#define cn const node
#define cQ const Queue
#define gc getchar
#define INF 1000000000
using namespace std;
int read() {
int x = 0; char c = gc();
while (!isdigit(c)) c = gc();
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
return x;
}
int n, a[maxn * 2];
char s[10];
stack<int> S;
int ans[maxn], c1;
int main() {
cin >> n;
for (int i = 1; i <= 2 * n; ++i) {
scanf("%s", s + 1);
if (s[1] == '+') a[i] = 0;
else scanf("%d", &a[i]);
}
for (int i = 2 * n; i; --i)
if (!a[i]) {
if (S.empty()) return puts("NO"), 0;
ans[++c1] = S.top(); S.pop();
}
else {
if (!S.empty() && a[i] > S.top()) return puts("NO"), 0;
S.push(a[i]);
}
puts("YES");
for (int i = n; i; --i) printf("%d ", ans[i]);
return 0;
}
|