P1878舞蹈课题解

hanzhang666 · 2021-04-26 13:23:37 · 题解

分析

这题还是很easy的。 主要是堆（优先队列）的运用。

大根堆：堆顶元素最大，像二叉树一样，越往下越数小。 相反小根堆：堆顶元素最小，像二叉树一样，越往下越数大。

定义默认为大根堆。

return，break,continue的区分。
return：停止某个函数。
break：停止最近的循环。
continue：结束该次循环。

代码

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;
}