P1878

miao5 · 2021-03-26 12:31:25 · 题解

首先定义一个people结构体，用于存储一对舞者的数据。 记得重载运算符，依据是舞蹈技术的差的大小。

输入的时候判断一下，如果性别不同就加入堆。

之后只要堆不是空的就一直循环。

记录堆顶的一对人。

只要两人都还没跳过舞，就让他们跳舞，就更新答案。

之后往左右找还在队里的人（因为跳完舞就出队所以现在他们就是相邻的了）。 找到了就入堆，没找到就执行下一对。

code（详细注释）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
char ch[200003];//输入性别的字符数组 
int a[200003];//输入舞蹈能力的数组 
bool vis[200003];//判断是否还在队中 
int ans1[200003],ans2[200003],t;//ans1和ans2存储答案，t存储答案数量 
struct people{
    int cha,x,y;//x和y分别是一组舞伴的编号，cha是他们舞蹈技术的差 
    friend bool operator < (people b,people c){
        //我们重新定义小于号，让舞蹈技术差最小的一对最靠前，如果有技术差一样的，编号小的靠前 
        if(b.cha==c.cha) return b.x>c.x;//如果两人舞蹈技术差一样，编号越小的越大 
        else return b.cha>c.cha;//否则技术差小的靠前 
    }
};
priority_queue<people> q;//定义一个people类型的大根堆 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ch[i];
    }//输入数据 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i!=1&&ch[i]!=ch[i-1]){//如果两人相邻且性别不同，入堆 
            q.push(people{abs(a[i-1]-a[i]),i-1,i});
        }
    }
    while(!q.empty()){//堆还没空 
        int x=q.top().x; 
        int y=q.top().y;//记录堆顶元素
        q.pop();//pop掉 
        if(!vis[x]&&!vis[y]){//如果两人还在队中 
            vis[x]=1;
            vis[y]=1;//标记出队 
            t++;//答案总数加一 
            ans1[t]=x;
            ans2[t]=y;//记录答案 
            while(x>=1&&vis[x]) x--;
            while(y<=n&&vis[y]) y++;//往左右继续找未出队的人 
            if(x<1||y>n) continue;//如果越界，就执行下一个 
            if(ch[x]!=ch[y])//如果不越界且性别不同，入堆 
            q.push(people{abs(a[x]-a[y]),x,y});
        }   
    }
    printf("%d\n",t);//输出t 
    for(int i=1;i<=t;i++) printf("%d %d\n",ans1[i],ans2[i]);//输出答案 
}