UVA-12657 Boxes in a Line (模拟，双向链表（数组实现）)

第一次对数组实现双向链表的练习，理解了发现数组实现真方便…

题目：UVA-12657

题目描述：
你有n个盒子在桌子上的一条线上从左到右编号为1……n。你的任务是模拟四种操作

1 X Y 移动盒子编号X到盒子编号Y的左边（如果X已经在Y的左边了就忽略）

2 X Y 移动盒子编号X到盒子编号Y的右边（如果X已经在Y的右边了就忽略）

3 X Y 交换盒子编号X与盒子编号Y的位置

4 将整条线反转

操作保证合法，X不等于Y

举一个例子，如果n=6，操作 1 1 4然后就变成了2 3 1 4 5 6；再操作 2 3 5就变成了 2 1 4 5 3 6；再操作 3 1 6 就变成 2 6 4 5 3 1；最后操作4，就变成了 1 3 5 4 6 2

分析：
这题用数组实现双向链表极其便利，因为这里的编号从1~n，即是 值 ，也是 下标（可以理解为node的地址），所以不需要另外创建node数组来联系这两者，直接就能处理。

分析一下题目，1，2操作直接模拟即可，3操作最好要对X,Y相邻的情况进行特判（不知道其他方法是否可省略特判，反正我WA了 ）。

操作4最为关键，如果每次都反转会花很多时间，一开始还不知道怎么处理，但其实反转只会影响操作1和操作2以及最后求和，如果反转了，操作1就变成了操作2，操作2变成了操作1，求和找奇数位置时从头到尾遍历变成从尾到头。

（还有，如果用switch语句来选择操作数，记得每个case结尾break;，不要问我为什么说这个 ）

贴下代码（里面还有注释）：

#include<cstdio>
using namespace std;
int Right[100001], Left[100001];
void link(int L, int R)    //构造一个函数来连接左右两个，可以让程序简洁明了很多
{
    Right[L] = R;Left[R] = L;
}
int main()
{
    int n, m,kase=1;while (scanf("%d%d",&n,&m)!=EOF){
    int i, k, x, y,head,tail;bool flag = true;         //用来标记操作4，true不反转，false反转for (i = 1; i <=n; i++)   //i即是编号，又是下标，直接串成双向链表link(i - 1, i);head = 0;                 //head做头节点Left[head] = 0;tail = n + 1;             //这个tail还是很重要的，不然链表第n个的操作就不方便了link(n, tail);Right[tail] = 0;while (m--){
    scanf("%d", &k);if (flag==false)      //当发现反转，仅影响操作1、操作2{
    if (k == 1)k = 2;else if (k == 2)k = 1;}switch (k){
    case 1:{
    scanf("%d%d", &x, &y);if (Left[y] == x)break;else{
    link(Left[x], Right[x]);link(Left[y], x);link(x, y);}break; }case 2:{
    	scanf("%d%d", &x, &y);if (Right[y] == x)break;else{
    link(Left[x], Right[x]);link(x, Right[y]);link(y, x);}break; }case 3:                     //注意特判相邻情况{
    scanf("%d%d", &x, &y);if (Right[x] == y){
    link(x, Right[y]);link(Left[x], y);link(y, x);}else if (Left[x] == y){
    link(y, Right[x]);link(Left[y], x);link(x, y);}else{
    int xleft = Left[x], xright = Right[x], yleft = Left[y], yright = Right[y];link(yleft, x);    //把x，y的左右都暂存，这样方便些，不然移动过程会发生变动link(x, yright);link(xleft, y);link(y, xright);}break;}case 4:flag = !flag;    //反转}}long long sum = 0;if (flag==true)    //正序查找奇数位置，从head到tail{
    i = Right[head];while (1){
    sum += i;if (Right[i] == tail)break;elsei = Right[i];if (Right[i] == tail)break;elsei = Right[i];}}else             //反转后倒序查找奇数位置，从tail到head{
    i = Left[tail];while (1){
    sum += i;if (Left[i] == head)break;elsei = Left[i];if (Left[i] == head)break;elsei = Left[i];}}printf("Case %d: %lld\n",kase++,sum);}return 0;
}