洛谷 P1878 舞蹈课 解题报告

P1878 舞蹈课

题目描述

有\(n\)个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为\(ABCD\)，那么\(BC\)出列之后队伍变为\(AD\)）。舞蹈技术相差最小即是\(a_i\)的绝对值最小。

任务是模拟以上过程，确定跳舞的配对及顺序。

输入输出格式

输入格式：

第一行为正整数\(n(1<=n<=2*10^5)\)：队伍中的人数。下一行包含\(n\)个字符\(B\)或者\(G\)，\(B\)代表男，\(G\)代表女。下一行为\(n\)个整数\(a_i(a_i<=10^7)\)。所有信息按照从左到右的顺序给出。在50%的数据中，n<=200。

输出格式：

第一行：出列的总对数\(k\)。接下来输出\(k\)行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。

---

思路：用二叉堆维护差值，用数组模拟链表，取出时判断是否已经用过即可。

---

Code:

#include <cstdio>

#include <queue>

using namespace std;

int abs(int x){return x>0?x:-x;}

const int N=200010;

struct node

{

    int l,r,w;

    node(){}

    node(int l,int r,int w)

    {

        this->l=l;

        this->r=r;

        this->w=w;

    }

    bool friend operator <(node n1,node n2)

    {

        if(n1.w==n2.w)

            return n1.l>n2.l;

        return n1.w>n2.w;

    }

};

priority_queue <node > q;

int score[N],color[N],vis[N],n,pre[N],suc[N],ans[N][2];

void init()

{

    char c;

    scanf("%d",&n);

    scanf("\n");

    for(int i=1;i<=n;i++)

    {

        scanf("%c",&c);

        if(c=='B') color[i]=1;

        pre[i]=i-1;suc[i]=i+1;

    }

    suc[n]=0;

    for(int i=1;i<=n;i++)

        scanf("%d",score+i);

    for(int i=1;i<n;i++)

        if(color[i]^color[i+1])

        {

            node t(i,i+1,abs(score[i]-score[i+1]));

            q.push(t);

        }

}

void work()

{

    int cnt=0;

    while(!q.empty())

    {

        int l=q.top().l,r=q.top().r;

        q.pop();

        if(vis[l]||vis[r]) continue;

        ans[++cnt][0]=l,ans[cnt][1]=r;

        vis[l]=vis[r]=1;

        if(!pre[l]||!suc[r]) continue;

        if(color[pre[l]]^color[suc[r]])

        {

            node t(pre[l],suc[r],abs(score[pre[l]]-score[suc[r]]));

            q.push(t);

        }

        suc[pre[l]]=suc[r];

        pre[suc[r]]=pre[l];

    }

    printf("%d\n",cnt);

    for(int i=1;i<=cnt;i++)

        printf("%d %d\n",ans[i][0],ans[i][1]);

}

int main()

{

    init();

    work();

    return 0;

}

---

2018.7.4