CF45C Dancing Lessons 题解

· · 题解

题意简述

有 n 个人顺序站成一排，不断选出能力，即 a_{i} 差值最小且相邻的男女（差值相同，选第一个人编号更小的），直到没有男女相邻。

大致思路

首先由于要从最小的差值选起，进行一些动态操作，于是我们可以想到使用一个优先差值升序、其次第一人编号升序的优先队列，存储每一对相邻男女的位置与差值。每次取出队首，直到队列为空。其次，我们考虑以下情况：\ 共有四人： 序号 性别 能力
1 男 1
2 女 3
3 男 4
4 女 6
队列中有如下元素： 序号 第一人位置 第二人位置 差值
1 2 3 1
2 1 2 2
3 3 4 2
经过一次操作后，取出第 2 个人和第 3 个人。 序号 性别 能力
1 男 1
4 女 6

我们发现，应当把队列中编号为 1、2、3 的、也就是二人中含有 2、3 的删除，处理这种个情况，我们可以使用一个 vis 数组标记无效的编号，如果队首元素含有无效编号，跳过即可。 另外，还需要添加一个：

序号 第一人位置 第二人位置 差值
1 1 4 5

于是，为了避免修改造成时间复杂度的增加，我们采用双向链表进行快速删除元素并快速得到选中二人的前一人、后一人，并将此二人连接并入队。\ 总体来讲，时间复杂度为 O(n \log n)，对于 1 \le n \le 2 \times 10^{5} ，可以通过。

关于初始化

本题的优先队列、链表均需初始化。

#include<iostream>
#include<queue> 
#include<cmath> 
using namespace std;
const int N=2e5+5;
struct Node{
    int pre,nxt,data;
    bool operator<(const Node &nd)const{//重载运算符，注意与实际相反 
        if(data==nd.data)return pre>nd.pre;
        return data>nd.data;
    }
}l[N],ans[N];//链表与记录答案的数组（借用一下pre和nxt，免再定义struct，实际用于优先队列） 
int a[N];//能力 
bool vis[N];//是否被选出 

priority_queue<Node> q;
int main(){
//输入 
    int n;
    string str;
    cin>>n;
    cin>>str;
    str=" "+str;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
//初始化 
    for(int i=1;i<n;i++){
        if(str[i]!=str[i+1]){
            q.push({i,i+1,abs(a[i+1]-a[i])});
        }
        l[i].nxt=i+1;
        l[i+1].pre=i;
    }
    int len=0;
    while(q.size()){//循环遍历队列 
        Node t=q.top();
        q.pop();
        if(vis[t.pre] || vis[t.nxt])continue;//被取出过 
        vis[t.pre]=vis[t.nxt]=true;//标记 
        ans[++len]={t.pre,t.nxt,t.data};
        int pre=l[t.pre].pre;//第一个人的前一个人 
        int nxt=l[t.nxt].nxt;//第二个人的后一个人 
        if(pre*nxt==0)continue;//有一个为0（0代表没有前/后一个） 
        if(str[pre]!=str[nxt]){
            q.push({pre,nxt,abs(a[nxt]-a[pre])});
        }
        //删除 
        l[pre].nxt=nxt;
        l[nxt].pre=pre;
    }
//输出 
    cout<<len<<'\n';
    for(int i=1;i<=len;i++){
        cout<<ans[i].pre<<" "<<ans[i].nxt<<'\n';
    }
    return 0;
}