题解 CF45C 【Dancing Lessons】

Sayori · 2020-06-26 09:06:42 · 题解

Description

给出长度为 n 的一个男女序列，每次求出当前相邻舞蹈技术差值最小的一对相邻男女的位置，并把他们从序列中删除，直到不存在相邻男女

Solution

看到序列中的删除操作，就能想到用链表去维护这个序列，而求舞蹈技术差值最小，则可以用优先队列去维护，将差值最小的放在最上面，每次求的时候在更新一下链表即可

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int pre[N], nex[N], a[N], fl[N];//fl数组用来标记当前位置是否使用
char s[N];
int n, cnt, ans[N][2];
struct node{
    int l, r, d;
    node(int L, int R, int D):l(L), r(R), d(D){}
    bool operator <(const node &o)const{
        return d == o.d ? l > o.l : d > o.d;//当二者差值相同时，按照l排序
    }
};
priority_queue<node> q;
template <typename T>
inline void read(T &x){
    char t(getchar()), flg(0); x = 0;
    for (; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args){read(x);read(args...);}
int main(){
    read(n);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i)
        read(a[i]), pre[i] = i - 1, nex[i] = i + 1;//初始化
    for(int i = 1; i < n; ++i)
        if(s[i] != s[i + 1])
            q.push(node(i, i + 1, abs(a[i] - a[i + 1])));
        //当两者性别不同时，即可插入优先队列
    while(!q.empty()){
        node tmp = q.top(); q.pop();//取出差值最小
        if(fl[tmp.l] || fl[tmp.r]) continue;//若当前节点访问过，就可以跳过
        ans[++cnt][0] = tmp.l, ans[cnt][1] = tmp.r;
        fl[tmp.l] = fl[tmp.r] = 1;
        int L = pre[tmp.l], R = nex[tmp.r];
        nex[L] = R, pre[R] = L;//维护链表
        if(L < 1 || R > n) continue;
        if(s[L] != s[R])
            q.push(node(L, R, abs(a[L] - a[R])));
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; ++i)
        printf("%d %d\n", ans[i][0], ans[i][1]);
}