题解 P1878 【舞蹈课】

VioletIsMyLove · 2020-07-29 18:45:06 · 题解

拿到题目，就知道这道题是要用堆优化。

首先预处理一趟，将刚开始相邻的男女的位置以及他们的差值丢进一个结构体堆中，然后对这个结构体重载一下子运算符，

bool operator <(const date B)const{return x<B.x||x==B.x&&L<B.L;}

，重载之后进行处理就会方便许多。

每次取出差值最小的男女，之后开个bool类型vis数组将其标记一下，然后用L和R找到其左边最近的没有被取走的Boy或Girl和右边的(vis就是起这个作用),然后判断一下左右最近的人是否为异性，是异性就将其丢进堆中，不是就不管他。

Code:

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,cnt,hep_size,a[maxn];
char S[maxn];
bool vis[maxn];
struct data{int L,R;}ans[maxn];
struct date{
    int x,L,R;
    bool operator <(const date B)const{return x<B.x||x==B.x&&L<B.L;}
}hep[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-')f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void put(int x,int L,int R){
    hep[++hep_size]=(date){x,L,R};int son=hep_size;
    while (son!=1&&hep[son]<hep[son>>1]) swap(hep[son],hep[son>>1]),son>>=1;
}
void get(int &L,int &R){
    if (!hep_size) {L=R=0;return;}
    L=hep[1].L,R=hep[1].R;hep[1]=hep[hep_size--];
    int son,fa=1;
    while (fa<<1<=hep_size){
        if ((fa<<1|1)>hep_size||hep[fa<<1]<hep[fa<<1|1]) son=fa<<1;else son=fa<<1|1;
        if (hep[son]<hep[fa]) swap(hep[son],hep[fa]),fa=son;else break;
    }
}
int main(){
    n=read();
    scanf("%s",S+1);
    for (int i=1;i<=n;i++){
        a[i]=read();
        if (i==1) continue;
        if (S[i]^S[i-1]) put(abs(a[i]-a[i-1]),i-1,i);
    }
    while (hep_size){
        int L,R;get(L,R);
        while (vis[L]||vis[R]) get(L,R);
        if (!L&&!R) break;
        ans[++cnt]=(data){L,R};
        vis[L--]=vis[R++]=1;
        while (L>=1&&vis[L]) L--;
        while (R<=n&&vis[R]) R++;
        if (L>=1&&R<=n&&S[L]^S[R]) put(abs(a[R]-a[L]),L,R);
    }
    printf("%d\n",cnt);
    for (int i=1;i<=cnt;i++) printf("%d %d\n",ans[i].L,ans[i].R);
    return 0;
}