题解 P1878 【舞蹈课】

荣一鸣 · 2018-07-07 15:26:57 · 题解

每次这群人里都要选择能力差值最小的一对男女来跳舞，而且组数也会有变化，所以我们想到了用堆优化

我们先将每一对相邻的异性之间能力的差值读入，然后用priority_queue来模拟堆

每当取出最上面的一对时要判断这一对是否合法（即这一对中是否有一人已经被配对。我们可以定义vis数组来记录是否是配对过。

这道题就是检验堆的使用的

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
struct node{
    int id;
    bool fem;
    int dan;
    int pre;
    int next;
};
struct de{
    int d;
    int ida;
    int idb;
    bool operator < (const de x) const{
        if(d==x.d){
            return ida>x.ida;
        }
        return d>x.d;
    }
};
struct ptt{
    int id1,id2;
};
int n,k;
int B,G;
int head;
int tail;
node peo[200010];
int vi[200010];
priority_queue<de> q;

int main(){
    scanf("%d",&n);
    peo[0].next=1;
    for(int i=1;i<=n;i++){
        peo[i].pre=i-1;
        peo[i].next=i+1;
        peo[i].id=i;
        char c;
        cin>>c;
        if(c=='B'){
            peo[i].fem=false;
            B++;
        }
        else{
            peo[i].fem=true;
            G++;
        }
    }
    head=0;
    tail=n+1;
    k=min(B,G);
    for(int i=1;i<=n;i++){
        scanf("%d",&peo[i].dan);
    }
    for(int i=1;i<n;i++){
        if(peo[i].fem^peo[i+1].fem){
            q.push((de){abs(peo[i].dan-peo[i+1].dan),i,i+1});
        }
    }
    cout<<k<<endl;
    int l=0;
    while(!q.empty()){
        de x=q.top();
        q.pop();
        if(vi[x.ida]|vi[x.idb]){
            continue;
        }
        cout<<x.ida<<" "<<x.idb;
        l++;
        if(l==k) break;
        cout<<endl;
        vi[x.ida]=vi[x.idb]=1;
        int a=peo[x.ida].pre,b=peo[x.idb].next;
        if(peo[a].fem^peo[b].fem){
            if(a<=0||b>n) continue;
            q.push((de){abs(peo[a].dan-peo[b].dan),a,b});
        }
    }
    return 0;
}