[Codeforces1092D1&D2] Tree with Maximum Cost(栈)

题目链接:
http://codeforces.com/contest/1092/problem/D1
http://codeforces.com/contest/1092/problem/D2
题意:
希望用$2\times 1$的砖头搭出一面长为$n$并且每一个单位长度高度为$a_i$的墙,现在允许的操作是:
D1:横、竖都允许放
D2:只允许横着放
问是否能搭出指定高度的墙?

D1:可以贪心,由于当两个相邻的墙高度的奇偶性相同的时候,那么这两个墙可以看做一面墙,并且高度可以任意(允许任意+1)。于是我们考虑维护一个栈,从左到右贪心地判断当前墙是否与栈顶的墙高度的奇偶相同,如果相同则配对出栈,否则入栈等待与它配对的墙。当栈内为空或只有一个高度的时候(此时这个高度可以搭成比之前所有墙都高的情况,并且前面的墙总可以+1到这个高度),则说明可以搭出指定高度的墙。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 200200;
int n;
int a[maxn];
stack<int> st;

signed main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
while(!st.empty()) st.pop();
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] &= 1;
}
for(int i = 1; i <= n; i++) {
if(st.empty()) {
st.emplace(a[i]);
continue;
}
if(st.top() != a[i]) st.emplace(a[i]);
else st.pop();
}
if(st.size() <= 1) puts("YES");
else puts("NO");
}
return 0;
}

D2:考虑只允许横着放,那么只有在两个块一样高的时候才能+1. 于是考虑扫到每一个数的时候是否与栈顶这个数相同,如果相同的话则可以配对出栈;否则讨论一下大小:如果当前块比栈顶的高,那就不会再有机会更新到栈顶那个块,于是这种情况下是没有解的,否则还是有可能存在解的。有一个cha点在输出前,如果栈内存在元素那么这个块一定是最高的(其他所有块结对后+1直到这个块),否则是没有解的。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 200200;
int n;
int a[maxn];
stack<int> st;

signed main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
int hi = 0;
while(!st.empty()) st.pop();
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
hi = max(hi, a[i]);
}
bool flag = 1;
for(int i = 1; i <= n; i++) {
if(st.empty()) {
st.emplace(a[i]);
continue;
}
if(st.top() == a[i]) st.pop();
else if(st.top() < a[i]) {
flag = 0;
break;
}
else st.emplace(a[i]);
}
if(!flag) {
puts("NO");
continue;
}
if(st.empty()) {
puts("YES");
continue;
}
if(st.size() == 1 && st.top() == hi) puts("YES");
else puts("NO");
}
return 0;
}