题解 P1878 【舞蹈课】

moye到碗里来 · 2017-09-23 17:02:27 · 题解

标准的优先队列，很多大佬都手写堆啊，我觉得没必要，基本不会卡你stl的。。

vist存是否配对过，while配对过直接跳过，直到两端或者不为配对过的就行了，还有就可以存两端位置，直接更新，有点像链的那种存储。

优先队列判定加个如果相等就取左边小的，很明显可以证明不可能存在交叉，所以一定是对的。

上代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,c;
    bool operator<(const node &p)const{
        if(p.c==c)
        {
            return p.x<x;
         } 
        return p.c<c;
    }
 };
priority_queue<node>que;
int cnt=0;
struct part
{
    int x,y;
}partner[100005];
int abs(int x,int y)
{
    return x<y?y-x:x-y;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,a[200005];
bool vis[200005];
char c[200005];
int main()
{
//    freopen("dancingLessons.in","r",stdin);
    //freopen("dancingLessons.out","w",stdout);
    n=read();
    scanf("%s",c);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        node t;
        if(i>1)
        if(c[i-1]!=c[i-2])
        {
                t.x=i-1;
                t.y=i;
                t.c=abs(a[i],a[i-1]);
                que.push(t);
        }    
    }
    bool flag;
    while(!que.empty())
    {
        flag=0;
        node t=que.top();
        que.pop();
        if(vis[t.x]||vis[t.y])
        continue;
        partner[++cnt].x=t.x;
        vis[t.x]=true;
        partner[cnt].y=t.y;
        vis[t.y]=true;
        while(vis[t.x-1])
        {
            if(t.x<=2)
            {
                flag=1;
                break;
            }
            t.x--;
        }
        if(flag==1)
        continue;
        while(vis[t.y+1])
        {
            if(t.y>=n-1)
            {
                flag=1;
                break;
            }
            t.y++;
        }
        if(flag==1)
        {
            continue;
        }
        //cout<<c[1]<<" "<<c[4];
        if(c[t.x-2]!=c[t.y]&&t.x>1&&t.y<n)
        {
            t.x=t.x-1;
            t.y=t.y+1;
            t.c=abs(a[t.x],a[t.y]);
            que.push(t);
        }    
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    {
        printf("%d %d\n",partner[i].x,partner[i].y);
     } 
}