题解 P1878 【舞蹈课】

chager · 2018-08-13 13:24:51 · 题解

某位蒟蒻的题解：
这道题是可以用小根堆做的。用的时候用一个结构体存储两个舞伴以及他们的技术差。每次从堆顶取一个结构体出来，判断两个舞伴是否用过，用过跳，没用过存起来，判断两个舞伴出列后有没有新的舞伴产生。
下面附代码：

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
int a[300010],c[10000010],ac[300010],jl[300010][3];
char s[300010];
struct node
{
    int qi,ho,c;
}w[300010];
void swap(int i,int j)
{
    int y;
    y=a[i];
    a[i]=a[j];
    a[j]=y;
    y=w[i].qi;
    w[i].qi=w[j].qi;
    w[j].qi=y;
    y=w[i].ho;
    w[i].ho=w[j].ho;
    w[j].ho=y;
    y=w[i].c;
    w[i].c=w[j].c;
    w[j].c=y;
    return;
}
void cr()
{
    int i,j;
    j=a[0];
    i=a[0]/2;
    if(j==1)
        return;
    while(1)
    {
        if(a[i]<a[j] || a[i]==a[j] && w[i].qi<w[j].qi)
            break;
        if(a[i]>a[j] || a[i]==a[j] && w[i].qi>w[j].qi)
        {
            swap(i,j);
            j=i;
            i=j/2;
        }
        else
            break;
        if(j==1 || i==0)
            break;
    }
    return;
}
void pc()
{
    int i,j;
    swap(1,a[0]+1);
    i=2;
    j=1;
    while(1)
    {
        if(i>a[0])
            break;
        if(a[j]<a[i] && a[j]<a[i+1])
            break;
        if(a[i]>a[i+1] && i+1<=a[0] || a[i]==a[i+1] && w[i].qi>w[i+1].qi && i+1<=a[0])
            i++;
        if(a[j]>a[i] || a[j]==a[i] && w[i].qi<w[j].qi)
        {
            swap(i,j);
            j=i;
            i=j*2;
        }
        else
            break;
    }
    return;
}
int main()
{
    int i,j,n,m;
    scanf("%d\n",&n);
    scanf("%s",s+1);
    for(i=1;i<=n;i++)
        scanf("%d",&ac[i]);
    for(i=1;i<n;i++)
    {
        if((s[i]=='G' && s[i+1]=='B') || (s[i]=='B' && s[i+1]=='G'))
        {
            a[0]++;
            a[a[0]]=abs(ac[i]-ac[i+1]);
            w[a[0]].qi=i;
            w[a[0]].ho=i+1;
            w[a[0]].c=a[a[0]];
            cr();
        }
    }
//  printf("%d\n",a[0]);
    while(a[0])
    {
        int f=0;
/*      uv:
*/      if(c[w[1].qi] || c[w[1].ho])
        {
//          printf("%d %d\n",w[1].qi,w[1].ho);
            a[0]--;
            pc();
/*          goto uv;
*/          continue;
        }
        c[w[1].qi]=1;
        c[w[1].ho]=1;
//      printf("%d %d\n",w[1].qi,w[1].ho);
        jl[0][0]++;
        jl[jl[0][0]][1]=w[1].qi;
        jl[jl[0][0]][2]=w[1].ho;
        i=w[1].qi;
        j=w[1].ho;
        while(c[i]==1 && i>0)
        {
            i--;
        }
        while(c[j]==1 && j<=n)
        {
            j++;
        }
        if(i>=1 && j<=n && c[i]==0 && c[j]==0 && ((s[i]=='G' && s[j]=='B') || (s[i]=='B' && s[j]=='G')))
        {
            f=1;
        }
        a[0]--;
        pc();
        if(f)
        {
            a[0]++;
            a[a[0]]=abs(ac[i]-ac[j]);
            w[a[0]].qi=i;
            w[a[0]].ho=j;
            w[a[0]].c=a[a[0]];
            cr();
        }
    }
    printf("%d",jl[0][0]);
    for(i=1;i<=jl[0][0];i++)
        printf("\n%d %d",jl[i][1],jl[i][2]);
    puts("");
    return 0;
}

其中c数组判断数有没有用过，ac数组存储舞技，a数组与结构体w同步，a和w.c存舞伴的技术差，w.qi和w.ho分别存储前舞伴和后舞伴。