题解 UVA12657 【Boxes in a Line】

· · 题解

没什么好说的，就是用链表模拟就行了

为什么要用链表模拟呢？

因为纯数组的话每一次执行命令1，命令2会需要移动大量元素，导致TLE。

链表的话有两种实现方法，指针和数组。本人更喜欢用指针写链表，因为这样可以不去考虑数组开的不够大等等情况。

思路如下：

对于1和2，移动就相当于先删除x，再在指定位置（y前或后）插入一个x。

对于3，直接交换x和y的地址和值

对于4，直接加标记（不懂的看紫书）

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
struct Lst{     //链表
    Lst *prev, *next;       //prev是前驱（即上一个元素），next是后继（即下一个元素）
    int value;//元素的值
    Lst(int val = 0): prev(0), next(0), value(val){}
    //构造函数，构造得到一个值为val的节点，默认为0
};
Lst *End;   //建一个虚拟节点
Lst* addr[100000 + 5];  //保存每一个值（每一个盒子）所对应的地址
int size;   //链表的大小
void csh(){     //初始化，即构造虚拟节点
    End = new Lst;  //分配内存
    End->prev = End;    //前驱指向自己，下面后继一样的
    End->next = End;
}
Lst* Insert(Lst *it, int val){  //插入元素，把值为val的元素插到地址it的后面
    Lst *it2 = new Lst(val);
    it2->next = it->next;
    it->next->prev = it2;
    it2->prev = it;
    it->next = it2;
    size++; //大小+1
    return addr[val]=it2;   //保存val的地址
}
Lst* Erase(Lst *it){    //删除地址为it的元素
    Lst *res = it->next;
    it->next->prev = it->prev;
    it->prev->next = it->next;
    addr[it->value] = 0;
    delete it;  //立即释放内存，避免内存泄漏
    size--; //大小-1
    return res;
}
int main(){
    csh();  //初始化见上面
    int m, n, k = 0;//k用于输出"Case"后面的数字，因此要赋初值（我因此处没有赋初值WA了好多次，更气的是在本地运行时编译器居然给他赋了初值0，结果找了半天才找出来错）
    bool rev = false;   //标记是否被反转（不懂的自己看紫书）
    while(cin>> n>> m){
        for(int i = 1; i <= n; ++i)
            Insert(End, n - i + 1); //插入节点，不知道为什么插入“i”得到一条反过来的链
        while(m--){
            int op;
            cin>> op;
            switch(op){
                case 1:{    
                    int a, b;
                    cin>> a>> b;
                    Erase(addr[a]);
                    if(rev) Insert(addr[b], a);//*
                    else Insert(addr[b]->prev, a);//*
                    break;
                }
                case 2:{
                    int a, b;
                    cin>> a>> b;
                    Erase(addr[a]);
                    if(rev) Insert(addr[b]->prev, a);//*
                    else Insert(addr[b], a);//*
                    break;
                }
                case 3:{
                    int a, b;
                    cin>> a>> b;
                    addr[a]->value = b;
                    addr[b]->value = a;//交换a,b(题目中x，y)的值
                    swap(addr[a], addr[b]);//交换a,b的地址
                    break;
                }
                case 4:
                    rev = !rev;
                    break;
            }
/*调试语句        if(rev){
            for(Lst *it = End->prev; it != End; it = it->prev)
                cout<<(it->value)<<' ';
        }
        else{
            for(Lst *it = End->next; it != End; it = it->next)
                cout<<(it->value)<<' ';
        }
        cout<<endl; */  
        }   
        unsigned long long ans = 0;
        int s = -1;
        cout<<"Case "<<++k<<": ";
        if(rev){//*
            for(Lst *it = End->prev; it != End; it = it->prev, s = ~s)
                if(s & 1){  
                    ans += (it->value);
//                  cout<<(it->value)<<' ';
                }
        }
        else{//*
            for(Lst *it = End->next; it != End; it = it->next, s = ~s)
                if(s & 1){
                    ans += (it->value);
//                  cout<<(it->value)<<' ';
                }
        }
//    cout<<endl;
    cout<<ans<<endl;
    rev = false;
    while(size) Erase(End->next);
    }
    return 0;
}

注：打星号的语句分反转和没有反转2种情况，请读者自行体会