6-1 移动的小球

浏览数：29 / 时间：2015年06月11日

你有一些小球，从左到右依次编号为1，2，3，…，n，

你可以执行两种指令。其中A X Y表示把小球X移动到小球Y左边，B X Y表示把小球X移动到小球Y右边。指令保证合法，即X不等于Y。

输入小球个数n。指令条数m和m条指令，注意，1≤n≤500000，0≤m≤100000。

输出从左到右输出最后的小球序列。

样例输入

6 2
A 1 4
B 3 5

样例输出

2 1 4 5 3 6

两种方法

代码1：

#include<stdio.h>
const int MAXN=500000+10;
int n,A[MAXN];
int find(int x)
{
    for(int i=1;i<=n;i++)
       if(A[i]==x)
          return i;
    return 0;
}
void shift_circular_left(int a,int b)
{
    int t=A[a];
    for(int i=a;i<b;i++)
       A[i]=A[i+1];
    A[b]=t;
}
void shift_circular_right(int a,int b)
{
    int t=A[b];
    for(int i=b;i>a;i--)
        A[i]=A[i-1];
    A[a]=t;
}
int main()
{
    int p,q,x,y,m;
    char type[9];
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        A[i]=i;
    for(int i=0;i<m;i++)
    {
        scanf("%s %d %d",&type,&x,&y);
        p=find(x);
        q=find(y);
        if(type[0]==‘A‘)
        {
            if(q>p)
            shift_circular_left(p,q-1);
            else
            shift_circular_right(q,p);
        }
        else
        {
            if(q>p)
               shift_circular_left(p,q);
            else
               shift_circular_right(q+1,p);
        }
    }
    for(int i=1;i<=n;i++)
        if(i==1)
           printf("%d",A[i]);
        else printf("%d",A[i]);
    printf("\n");
    return 0;
}

代码2：

#include<stdio.h>
const int MAXN=1000;
int n,left[MAXN],right[MAXN];

void link(int X,int Y)
{
    right[X]=Y;
    left[Y]=X;
}

int main()
{
    int i,m,X,Y,first=1;
    char type[9];
    scanf("%d %d",&n,&m);
    right[0]=1;
    for(i=1;i<=n;i++)
    {
        left[i]=i-1;
        right[i]=i+1;
    }
    for(i=0;i<m;i++)
    {
        scanf("%s %d %d",&type,&X,&Y);
        link(left[X],right[X]);
        if(type[0]==‘A‘)
        {
            link(left[Y],X);
            link(X,Y);
        }
        else
        {
            link(X,right[Y]);
            link(Y,X);
        }
    }
    for(int X=right[0];X!=n+1;X=right[X])
        if(first)
        {
            printf("%d",X);
            first=0;
        }
        else
        printf("%d",X);
    printf("\n");
    return 0;
}