UVa12657 Boxes in a Line(移动盒子)的理解与解析 链表-双向链表

UVa12657 Boxes in a Line(移动盒子)的理解与解析 链表-双向链表

Solution

链表-双向链表

#include 
#include 

using namespace std;
const int maxn=100000+5;
int n,leftt[maxn],rightt[maxn];//left and right is ambiguous

void link(int L,int R)
{
    rightt[L]=R;leftt[R]=L;
}

int main()
{
    int m,kase=0;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=1;i<=n;i++){
            leftt[i]=i-1;
            rightt[i]=(i+1)%(n+1);
        }
        rightt[0]=1;leftt[0]=n;
        int op,X,Y,inv=0;

        while(m--){
            scanf("%d",&op);
            if(op==4) inv=!inv;
            else{
                scanf("%d%d",&X,&Y);
                if(op==3&&rightt[Y]==X) swap(X,Y);//!为了转化为同一种情况来处理，x、y只是一个代号，反正结果变得是值
                if(op!=3&&inv) op=3-op;
                if(op==1&&X==leftt[Y]) continue;
                if(op==2&&X==rightt[Y]) continue;

                int LX=leftt[X],RX=rightt[X],LY=leftt[Y],RY=rightt[Y];
                //下面分类讨论，不要漏掉
                if(op==1){
                    link(LX,RX);link(LY,X);link(X,Y);
                }//X的左右连起来，X和Y左，X和Y
                else if(op==2){
                    link(LX,RX);link(Y,X);link(X,RY);
                }//X的左右连起来，Y和X，X和Y右    按照链的顺序来写，可能思路更清晰
                else if(op==3){
                    if(rightt[X]==Y) {link(LX,Y);link(Y,X);link(X,RY);}
                    else {link(LX,Y);link(Y,RX);link(LY,X);link(X,RY);}
                }
            }
        }

        int b=0;
        long long ans=0;
        for(int i=1;i<=n;i++){
            b=rightt[b];//向右推移
            if(i%2==1) ans+=b;
        }
        if(inv&&n%2==0) ans=(long long)n*(n+1)/2-ans;//如果n不是偶数的话，倒一下结果也一样
        printf("Case %d:  %lldn",++kase,ans);
    }
    return 0;
}

谢谢