题解 P1878 【舞蹈课】

· · 题解

这一题大概是二叉堆也就是优先队列的题。

首先新建一个小根堆

按照题意模拟一下过程：第一遍，我们从左到右扫整个数组，如果有相邻的异性就入队。

这里在优先队列里我们存储三个信息：当前一对的编号 (x,y) 以及它们的差的绝对值，每次先是按照绝对值从小到大排序，然后如果绝对值一样就按照左端点从小到大排序即可。

每一次首先从优先队列里去处队首元素，将他们标记为已取过，出队，用 ans 数组进行记录。

看到这里，此题似乎与优先队列裸题没区别。

但是题目里说了这么一句：“一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD ）”。

这意味着什么呢？AD 仍然有可能组成一对新的合法的舞伴，但是我们在第一遍扫描的时候无法考虑这种情况。

怎么办？链表

设 f[i] 表示右边和i相邻的数，g[i] 表示左边和i相邻的数。这样的话呢，就形成了指向关系。

首先将 f[i] 初始化成 i+1 ，g[i] 初始化成 i-1（这里比较好理解）。

然后每次进行合法的出队的操作的时候，我们把当前点对的左边的数叫 x，右边的数叫 y 那么 x 的左边相邻点的右边相邻点自然就要指向 y 的右边相邻点，y 的右边相邻点的左边相邻点自然要指向 x 的左边相邻点。

这里有点绕，简而言之就是（可以画个图试试）。

f[g[x]] = f[y];

g[f[y]] = g[x];

然后这里多出来了一对新的相邻点 g[x] 和 f[y]。

判断他们是否合法，如果合法就入队即可。

代码：

#include<bits/stdc++.h>

using namespace std;
struct node{
    int w,c,d;
};
priority_queue<node>q;
int n,a[200011]={0},is[200011]={0},cnt=0,ans1[200011]={0},ans2[200011]={0},f[200011]={0},g[200011]={0},flag=1;
bool operator<(node a,node b){
    if(a.w==b.w)return a.c>b.c;
    else return a.w>b.w;
}
string s;
int main(){
    cin>>n;
    cin>>s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    s+='H';
    for(int i=1;i<n;i++){
        if(s[i-1]!=s[i])q.push((node){abs(a[i]-a[i+1]),i,i+1});
    }
    for(int i=1;i<=n;i++){
        f[i]=i+1;
        g[i]=i-1;
    }
    while(q.empty()==0){
        node t=q.top();
        q.pop();
        int x=t.c,y=t.d;
        if(is[x]==0&&is[y]==0){
            f[g[x]]=f[y];
            g[f[y]]=g[x];
            cnt+=1;
            ans1[cnt]=x,ans2[cnt]=y;
            is[x]=1,is[y]=1;
            if(is[g[x]]==0&&is[f[y]]==0){
                if((s[g[x]-1]+s[f[y]-1])==('G'+'B')){
                    q.push((node){abs(a[g[x]]-a[f[y]]),g[x],f[y]});
                }
            }
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
        cout<<ans1[i]<<" "<<ans2[i]<<endl;
    }
    return 0;
}

最后提示一点，一定一定要先出队（具体就是用 t 记录队首信息以后就立刻 POP）。

否则会WA（因为已经有新的数进来了队首可能就变了我就是在这卡住的）

都到这了，点个赞好吗qwq