Codeforces 899E Segments Removal

链接

传送门

题意

给出$n$个数的序列,每次删除最长连续相同子序列中最靠左的一个。如$[13,13,7,7,7,2,2,2]$在一次删除操作之后将变为$[13,13,2,2,2]$。输出使序列为空的最少操作次数。

思路

用map和set分别存每个连续相同子序列的起点、长度和元素值.在set中找到最长连续相同子序列中最靠左的一个之后删除掉,在map中合并该序列前后两个连续子序列,然后删除该序列,再把更新的序列写回set。这样操作直到set为空。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#define X first
#define Y second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
map<int, pii> dict;
set<piii> s;
int main() {
int n;
scanf("%d", &n);
int pos = -1, val = -1, num = 0;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
if (x != val) {
if (val != -1) {
dict[pos] = make_pair(num, val);
s.insert(make_pair(num, make_pair(n - pos, val)));
}
pos = i, val = x, num = 1;
} else {
++num;
}
}
dict[pos] = make_pair(num, val);
s.insert(make_pair(num, make_pair(n - pos, val)));
int ans = 0;
while (!s.empty()) {
++ans;
piii k = *(--s.end());
s.erase(k);
pos = n - k.Y.X, val = k.Y.Y, num = k.X;
auto it = dict.find(pos);
if (it != dict.begin()) {
auto it1 = it;
--it1;
auto it2 = it;
++it2;
if (it2 != dict.end()) {
if (it1 -> Y.Y == it2 -> Y.Y) {
s.erase(make_pair(it1 -> Y.X, make_pair(n - it1 -> X, it1 -> Y.Y)));
it1 -> Y.X += it2 -> Y.X;
s.insert(make_pair(it1 -> Y.X, make_pair(n - it1 -> X, it1 -> Y.Y)));
s.erase(make_pair(it2 -> Y.X, make_pair(n - it2 -> X, it2 -> Y.Y)));
dict.erase(it2);
}
}
}
dict.erase(it);
}
printf("%d\n", ans);
return 0;
}

支付宝扫码领红包