这是我们考试题，我做了 $75$ 分，最后才发现是元素入队的时候没有赋值……

Problem

有一个长度为 $n$ 的整数数组，对数组执行若干次操作。每一次找到连续相等整数的最长段（如果有多个段长度相同，选择最靠左边的段）并删除它。要求计算经过多少次操作后数组为空。

Solution

因为前两天才调完小熊的果篮，记忆犹新，所以立刻想到了队列+链表的做法。然后再读题，发现需要找长度最长的区间，不能用普通队列，要用优先队列。

我们先把所有的区间都找出来，存储每一个区间的左端点，长度（这样就可以算出右端点了）和这个区间数字的值。然后把这些区间全部按照顺序弄到一个双向链表里面，并把需要的值加入优先队列。

详细的讲解在代码注释里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 定义结构体，需要存区间左端点，区间长度和它在链表里的下标
struct node { int l, len, id; };
std::priority_queue<node> q;
// 定义排序规则：区间长度，一样时左边优先
bool operator<(node x, node y) { return (x.len != y.len) ? (x.len < y.len) : (x.id > y.id); }

// lst 为上一个区间的左端点，因为我们要计算区间长度，所以需要用这个区间和上个区间的左端点算上一个区间的长度，需要存一下
int ans = 0, lst = 0; 
a[0] = a[n + 1] = -1; // 特殊处理头尾端点，以免错误合并
rep(i, 1, n) {
    if(a[i] != a[i - 1]) { // 说明这个数是一个区间的开头
        num[++k] = a[i];
        l[k] = k - 1; // 初始化链表
        r[k] = k + 1;
        if(k != 1) { // 如果这个区间有上一个，即不是第一个
            q.push(node({lst, i - lst, k - 1})); // 元素入队
            L[k - 1] = lst, LEN[k - 1] = i - lst; // 记录区间左端点和长度
        }
        lst = i; // 更新上一个区间的左端点
    }
}
q.push(node({lst, n - lst + 1, k})); // 最后一个区间也需要处理
L[k] = lst, LEN[k] = n - lst + 1;
r[0] = 1, l[k + 1] = k; // 链表的初始化

接着就是核心代码了。

我们用一个 bool 数组标记一个区间是否被取过，然后从队列里面不停取元素。

  • 若此区间已经被标记过了就直接跳过。
  • 若此区间没有被取过，就标记一下这个区间，此时又取了一个区间，答案需要 $+1$，然后检查一下它的左右两个区间是否需要被合并；如果需要，就把两个区间合并到它左边那个区间，并标记它右边那个区间。

这句话信息量有点大，是什么意思呢？

说明我们拿到一个没被取过的区间时，需要做这几件事：

  1. 把这个区间标记为“已经被取过”。
  2. 因为又取了一个区间，所以答案要 $+1$。
  3. 把这个区间从链表里删掉。
  4. 检查这个被删除的区间的左边的区间（命名为 $l$）和它右边的区间（命名为 $r$）是否需要被合并，也就是说这两个区间的值是不是一样的，如果是一样的，那这个区间被取了之后，$l$ 和 $r$ 就变成了一个区间，所以需要被合并。
  5. 合并两个区间的时候，可以把 $l$ 的长度改为两个区间的长度相加，然后把 $r$ 删掉。需要注意 $r$ 也要被标记。
  6. 把更新的 $l$ 加入队列。

这个时候就会有小朋友问了：此时队列里还有原来的 $l$，是不是需要删掉？

答案是不需要。因为优先队列的排序规则是按照长度从大到小排的，所以更新后的 $l$ 一定会比原来的 $l$ 先取出，取出之后我们就标记了 $l$，也就不会重复取到了。

给一下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline void remove(int x) {
    id_use[x] = 1; // 实现时可以把标记的代码放在删除的函数里面
    r[l[x]] = r[x];
    l[r[x]] = l[x];
    return;
}

while(!q.empty()) {
    while(!q.empty() && id_use[q.top().id]) // 过滤掉已经被标记过的点
        q.pop();
    if(q.empty()) // 如果队列被取空了就直接跳过
        break;
    node u = q.top();
    q.pop();
    ++ans; // 更新答案
    if(num[r[u.id]] == num[l[u.id]]) { // 如果 l 和 r 需要被合并
        LEN[l[u.id]] += LEN[r[u.id]]; // 赋值，注意这里不写只能得 75 分
        q.push(node({L[l[u.id]], LEN[l[u.id]], l[u.id]})); // l 入队
        remove(r[u.id]); // 删除 r
    }
    remove(u.id); // 把这个区间删除
}
write(ans - 1); // 这里 -1 是因为头和尾会被错误合并，所以会多一次

大概就是这样了吧。因为核心代码已经给出，所以不再给完整代码了。

另外就是祝贺一下 ljt 考试的时候终于没有写挂快读快写了。