题解：CF45C Dancing Lessons

· · 题解

Description

有一个长度为 n 的带权 01 串，每次删除相邻且不同，权值之差最小的一对字符并输出，直至 01 串全部相同为止。若有多对，则先删最左边的。

Solution

类似这种题，其实做多了都能一眼看出套路。

由于题目要求先输出权值之差最小的，如果每次都 sort 一遍显然过劣。如何维护动态最小值呢？自然是想到用小根堆维护：先将所有合法的字符对加入堆中，每次取出堆顶，更新答案，然后删除元素，最后更新小根堆，即判断删除后该点左右两边是否不同，不同就加入堆中。

如何删除元素？对于动态维护序列相邻关系，双向链表显然最为高效。于是，优先队列 + 双向链表这个数据结构诞生，本题也就迎刃而解。

但双向链表还需注意边界问题，因为 l_1=0，r_n=n+1，这是我们不想更新的点。这里有个比较方便的处理方式：用 vis 记录该点是否被删除，初始化时 vis_0=1，vis_{n+1}=1，即可。常见的处理方式还有将 val_0，val_{n+1} 赋成极大极小值，保证不会用来更新答案。

像优先队列 + 双向链表这种数据结构还是挺常见的，大多会与贪心结合在一起就变成蓝的了。试试这个

Code

char op[SIZE];
int n, s[SIZE], v[SIZE];

int idx[SIZE], idy[SIZE], cnt;
//记录答案
int l[SIZE], r[SIZE], vis[SIZE];
//l r 为双向链表，vis 记录是否被删除了

struct node {
    int i, j, val;
    bool operator < (const node&nd) const {
        return val == nd.val? i > nd.i: val > nd.val;
        //细节 1：
        //因为下面建立的是大跟堆，想要维护最小值需要重载小于号成大于号
    }
};
priority_queue<node> q;

int main() {
    scanf("%d %s", &n, op + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = op[i] == 'B'? 0: 1;
        //转成 01 串
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", v + i);
        l[i] = i - 1, r[i] = i + 1;
        if(i > 1 && s[i-1] != s[i]){
            q.push({i - 1, i, abs(v[i - 1] - v[i])});
        }
        //添加候选集合
    }      
    vis[0] = vis[n + 1] = 1;
    //细节 2
    while (!q.empty()) {
        int i = q.top().i, j = q.top().j;
        q.pop();
        if (vis[i] || vis[j]) continue;
        idx[++cnt] = i, idy[cnt] = j;
        vis[i] = vis[j] = 1;
        int x = l[i], y = r[j];
        r[x] = y, l[y] = x;
        //Del
        if (s[x] != s[y] && ! (vis[x] || vis[y])) {
            q.push({x, y, abs(v[x] - v[y])});
        }
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++) {
        printf("%d %d\n", idx[i], idy[i]);
    }
    return 0;
}