题解 UVA12657 【移动盒子 Boxes in a Line】

· · 题解

调了2天才写对，我真是太弱了！

要在中间插入，用数组的话要全体向后移一位。显然复杂度肯定爆了！那就用链表吧。好像没有其他好的数据结构了（或者是我没想到，毕竟我很弱）。

由于复杂度的问题最烦的就是4操作。如果枚举把链表倒过来复杂度照样超。于是我们发现链表的顺序只对1、2操作的左右和最后输出有影响。于是如果现在链表是倒着的并且执行1、2操作，那就换一下（是1则变2，否则变1）。输出的话如果n是奇数的话怎么反转都是把奇数位加起来。但n是偶数的话则分两种情况：

  1. 转了奇数次，相当于转了1次，输出偶数位
  2. 转了偶数次，相当于没转，输出奇数位

还有，如果3操作交换是，要特判两数相邻的情况，我卡了好久！

最后就上代码吧（请忽略我那丑陋的马蜂QWQ）：

#include<stdio.h>
#include<iostream>
#define MAXN 100005
using namespace std;
struct node
{
    int data;
    node *next;
};
int n,m,id;
node *zhi[MAXN];
bool flag;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ++id;//第几组数据，输出时用 
        flag=1;//顺序正序，0则为倒序 
        node *head=new node;//新的head 
        head->next=NULL;//初值 
        node *ptr=head;//记录上一个指针 
        for(int i=1;i<=n;++i)
        {
            node *p=new node;//新的指针 
            p->next=NULL;//目前下一个为空 
            p->data=i;//数为i 
            ptr->next=p;//上一个数的next指向p 
            zhi[i]=ptr;//这个数的上一个数的指针为ptr 
            ptr=p;//更新ptr 
        }
        for(int i=1;i<=m;++i)
        {
            int k,x,y;
            scanf("%d",&k);
            if(!flag&&(k==1||k==2))//如果倒序又是与左右有关系 
                k=3-k;//交换 
            if(k==1)
            {
                scanf("%d%d",&x,&y);
                node *p=zhi[x]->next;
                zhi[x]->next=zhi[x]->next->next;
                if(zhi[x]->next)
                    zhi[zhi[x]->next->data]=zhi[x];
                /*删掉x的位置*/ 
                p->next=zhi[y]->next;
                zhi[y]->next=p;
                zhi[x]=zhi[y];
                zhi[p->next->data]=p;
                /*把x放到y的左边*/
            }
            else if(k==2)
            {
                scanf("%d%d",&x,&y);
                node *p=zhi[x]->next;
                zhi[x]->next=zhi[x]->next->next;
                if(zhi[x]->next)
                    zhi[zhi[x]->next->data]=zhi[x];
                /*删掉x的位置*/ 
                p->next=zhi[y]->next->next;
                zhi[y]->next->next=p;
                zhi[x]=zhi[y]->next;
                if(p->next)
                    zhi[p->next->data]=p;
                /*把x放到y的右边*/ 
            }
            else if(k==3)
            {
                scanf("%d%d",&x,&y);
                if(zhi[y]->next==zhi[x])//x是y的下一个，方便起见交换一下，反正没有顺序 
                    swap(x,y);
                if(zhi[x]->next==zhi[y])//相邻 
                {
                    node *p=zhi[x]->next,*q=zhi[y]->next;
                    zhi[x]->next=q;
                    p->next=q->next;
                    q->next=p;
                    zhi[y]=zhi[x];
                    zhi[x]=q;
                    if(p->next)
                        zhi[p->next->data]=p;
                }
                else//不相邻 
                {
                    node *p=zhi[x]->next,*q=zhi[y]->next,*p1=p->next,*q1=q->next;               
                    zhi[x]->next=q,q->next=p1;
                    zhi[y]->next=p,p->next=q1;;
                    node *t=zhi[y];
                    zhi[y]=zhi[x];
                    zhi[x]=t;
                    if(p1)
                        zhi[p1->data]=q;
                    if(q1)
                        zhi[q1->data]=p;
                }
            }
            else//反转 
                flag=!flag;
        }
        bool ji=0;
        long long sum=0;//记得开long long哦 
        ptr=head;
        for(node *i=head->next;i;i=i->next)
        {
            ji=!ji;
            if(n%2&&ji)//n为奇数，第奇数个 
                    sum+=i->data;
            else if(!(n%2)&&flag&&ji)//n为偶数，第奇数个，反转偶数次 
                    sum+=i->data;
            else if(!(n%2)&&!flag&&!ji)//n为偶数，第偶数个，反转奇数次 
                    sum+=i->data;
            delete ptr;//防止内存泄漏，删了！ 
            ptr=i;//更新ptr 
        }
        delete ptr;//最后一个还没删，删了！ 
        printf("Case %d: %lld\n",id,sum);//输出 
    }
    return 0;
}

感谢阅读！点个赞再走呗