6 5 Boxes in a Line UVa12657 - nuaazdh/acm GitHub Wiki

##例题 6-5 移动盒子（Boxes in a Line, UVa127675） ###问题 给定一行盒子，从左到右编号依次为1，2，...，n.可以执行以下命令：

1 X Y 把盒子 X 移动到 Y 的左边（如果已经在左边，忽略此命令）

2 X Y 把盒子 X 移动到 Y 右边（如果X已经在Y的右边，忽略此命令）

3 X Y交换 X 和 Y 的位置

4 把整个顺序颠倒

指令保证合法，即X 不等于 Y， 输入包含不超过10组数据，每组第一行为盒子的数目n和指令的数目m(1<=n,m<=100000)。

样例输入：

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4

样例输出：

Case 1: 12
Case 2: 9
Case 3: 2500050000

###分析

如果用数组来求解，复杂度太高，每次要移动大量元素，因此很容易想到用双向链表求解。 当然可以用 自己构造双向链表，或者使用STL的list。受到前一题的启发，其实可用两个 int 数组来构造双向链表，next数组表示当前元素的下一个元素的下标，prev表示前一个元素的下标。

###code in C++

#include <iostream>

const int max_size = 100100;

int prev[max_size];
int next[max_size];

void swap_int(int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

void print_order() {
    int i;
    for (i = next[0]; i != 0; i = next[i]) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

void print_vorder()
{
    int i;
    for (i = prev[0]; i != 0; i = prev[i]) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

int main() {
    int m, n, cmd, x, y, i, j, inv = 0, kcase = 0;
    unsigned long long sum;

    while (std::cin >> m >> n && m && n) {
        sum = 0;
        inv = 0;
        for (i = 1; i <= m; ++i) {
            next[i] = i + 1;
            prev[i] = i - 1;
        }
        next[0] = 1;
        next[m] = 0;
        prev[0] = m;
        for (i = 0; i < n; ++i) {
            std::cin >> cmd;
            if (cmd == 4) {
                inv = 1 - inv;

            } else {
                if (inv) {
                    if (cmd == 1) cmd = 2;
                    else if (cmd == 2) cmd = 1;
                    if (cmd == 3) swap_int(x, y);
                }
                std::cin >> x >> y;
                if (cmd == 1) {
                    if (next[x] == y) {
                        continue;
                    }
                    prev[next[x]] = prev[x];
                    next[prev[x]] = next[x];
                    next[prev[y]] = x;
                    prev[x] = prev[y];
                    prev[y] = x;
                    next[x] = y;

                } else if (cmd == 2) {
                    if (prev[x] == y) {
                        continue;
                    }
                    if (next[x]) prev[next[x]] = prev[x];
                    next[prev[x]] = next[x];
                    if(next[y]) prev[next[y]] = x;
                    next[x] = next[y];
                    prev[x] = y;
                    next[y] = x;
                } else if (cmd == 3) {
                    if(prev[x] == y)
                        swap_int(x,y);
                    if(prev[y] == x){
                        next[prev[x]] = y;
                        prev[next[y]] = x;
                        prev[y] = prev[x];
                        next[x] = next[y];
                        prev[x] = y;
                        next[y] = x;

                    }else{
                        prev[next[x]] = y;
                        next[prev[x]] = y;
                        prev[next[y]] = x;
                        next[prev[y]] = x;
                        swap_int(prev[x], prev[y]);
                        swap_int(next[x], next[y]);
                    }
                }
            }// else
//            print_order();
//            print_vorder();
        }//for
        j = 1;
        for (i = next[0]; i != 0; i = next[i], j++) {
            if (inv && !(m & 1)) {
                if (j & 1) continue;
            } else {
                if (!(j & 1)) continue;
            }
            sum += i;
        }
        std::cout << "Case " << ++kcase << ": " << sum << "\n";
    }
    return 0;
}

###点评 调试了很久才AC，主要的注意点：

  1. next和 prev的初始化，
next[0]=0;
prev[0]=m;
  1. 执行命令 3时候，注意如果X和Y是相邻的，需要特殊处理；
  2. 对命令4的特殊处理，如果每次都调整代价太大，很容易超时，这里使用了一个标记；

###改进 书中采用了一个新的方法，思路大致相同，但是不在调整指针（prev和next ）的值，而是通过一个 link函数来连接链表的节点。

void link(int L, int R)
{
    next[L] = R;
    prev[R] = L;
}
⚠️ **GitHub.com Fallback** ⚠️