Codeforces 899E Segments Removal

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章