题解 P1878 【舞蹈课】

pipiispig · 2019-02-24 11:25:13 · 题解

这个题用stl来做很简答，于是我写了一个手写堆来模拟,用手写堆来实现却是比stl复杂的多QwQ;

如果不了解手写堆的可以baidu一下（我要Google！！！）；

#include<iostream>
#include<cmath>
using namespace std;
const int N=4*100005;
int n,cnt=0,sum=0;
char c[N];
int s[N];
int ans1[N],ans2[N],vis[N]; 
struct node{
    int x,y,w;
};
node heap[N];
void up(int x)
{
    int s=x;
    while(s>1)
    {
        if(heap[s].w<heap[s/2].w)
        {
            swap(heap[s],heap[s/2]);
            s>>=1;
        }
        else if(heap[s].w==heap[s/2].w&&heap[s].x<heap[s/2].x)
        {
            swap(heap[s],heap[s/2]);
            s>>=1;
        }
        else break;
    }
}

void down(int x)
{
    int s=x*2;
    while(s<=cnt)
    {
        if(s<cnt&&(heap[s].w>heap[s+1].w)||(heap[s].w==heap[s+1].w)&&heap[s].x>heap[s+1].x)s++;
        if(heap[s].w<heap[x].w)
        {
            swap(heap[s],heap[x]);
            x=s;
            s<<=1;
        }
        else if(heap[s].w==heap[x].w&&heap[s].x<heap[x].x)
        {
            swap(heap[s],heap[x]);
            x=s;
            s<<=1;
        }
        else break;
    }
}

int main()
{
    cin>>n;
    cin>>c;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    for(int i=1;i<n;i++)
    {
        if(c[i-1]!=c[i])heap[++cnt]=node{i-1,i,abs(s[i-1]-s[i])};
        up(cnt);
    } 
    while(cnt>0)
    {
        if(!vis[heap[1].x]&&!vis[heap[1].y])
        {
            ans1[++sum]=heap[1].x+1;
            ans2[sum]=heap[1].y+1;
            vis[heap[1].x]=1;
            vis[heap[1].y]=1;
            int x=heap[1].x;
            int y=heap[1].y;
            while(vis[x]&&x>0)x--;
            while(vis[y]&&y<n-1)y++;
            if(c[x]!=c[y])heap[++cnt]=node{x,y,abs(s[x]-s[y])};
        }//这个地方是唯一的难点，每次删除未被标记的堆顶元素时都要把它两边的未被标记的元素从新入堆，一个可以被证实的数据我放在了全文的结尾；
        heap[1]=heap[cnt--];
        down(1);
    }
    cout<<sum<<endl;
    for(int i=1;i<=sum;i++)
    {
        cout<<ans1[i]<<" "<<ans2[i]<<endl; 
    }//我这个地方没有想出比较简单可以求出sum的方法，只好把答案保存，最后输出.....
} 
}

一个小数据

20
BGBGBGGGBGGBGBBGBGGB
4 2 4 3 5 4 6 3 6 3 2 6 7 3 5 2 9 5 1 5

正确答案应该是

一个常见的错误答案如下