【UVA 12657】移动盒子 Boxes in a Line

【UVA 12657】移动盒子 Boxes in a Line

洛谷题目地址

【题意】

一行有n 个盒子，从左到右编号为1～n。模拟以下4种命令。

• 1 X Y ：将盒子X 移动到Y 的左侧（如果X 已经在Y 的左侧，则忽略此项）。
• 2 X Y ：将盒子X 移动到Y 的右侧（如果X 已经在Y 的右侧，则忽略此项）。
• 3 X Y ：交换盒子X 和Y 的位置。
• 4：翻转整行盒子序列。

命令保证有效，即X 不会 与 Y相等

【举例说明】

有6个盒子，执行1 1 4，即1移动到4的左侧，变成2 31 4 5 6。然后执行2 3 5，即3移动到5的右侧，变成2 1 4 5 3 6。接着执行3 1 6，即交换1和6的位置，变成2 6 4 5 3 1。最后执行4，即翻转整行序列，变成1 3 5 4 6 2。

【输入输出】

输入：

最多有10个测试用例。每个测试用例的第1行都包含两个整数n 和m （1≤n , m ≤100 000），下面的m 行，每行都包含一个命令。

输出：

对于每个测试用例，都单行输出奇数索引位置的数字总和。

【样例】

【思路分析】

这个题涉及大量的移动元素，看似使用链表很合适，实际上当咱们将盒子 X 移动到盒子Y 的左侧时，需要查找盒子X 和盒子Y 在链表中的位置，查找操作 是链表不擅长的，多次查找甚至会超时，所以不用list 链表实现。

这里可以使用既具有链表特性又具有快速查找能力的静态链表实现，因为在题目中既有向前操作，也有向后操作，因此选择静态双向链表。另外，有大量元素的链表，其翻转操作的时间复杂度很高，会超时，此时只需做标记即可，不需要真的翻转。

【算法设计】

1. 初始化双向静态链表（前驱数组为l []，后继数组为r[]），翻转标记flag=false。
2. 读入操作指令a 。
3. 如果a =4，则标记翻转，flag=!flag，否则读入x 、y 。
4. 如果a !=3&&flag，则a =3-a 。因为如果翻转标记为真，则左右是倒置的，1、2指令正好相反，即1号指令（将x 移到y 左侧）相当于2号指令（将x 移到y 右侧）。因此如果a =1，则转换为2；如果a=2，则转换为1。
5. 对于1、2指令，如果本来位置就是对的，则什么都不做。
6. 如果a =1，则删除x ，将x 插入y 左侧。
7. 如果a =2，则删除x ，将x 插入y 右侧。
8. 如果a =3，则考虑相邻和不相邻两种情况进行处理。

【算法中的基本操作】

① 链接。如将 L 和 R 链接起来，则L 的后继为 R，R的前驱为L

void link(int L , int R){ //将L和R 链接起来
	r[L] = R;
	l[R] = L;
}
1
2
3
4

② 删除。删除x 时，只需要将 x 跳过去，将x 的前驱和后继链接起来即可。

link(Lx , Rx);  //删除x
1

③ 插入(将 x 插入 y左侧)。将 x 插入 y 左侧时，先删除x，然后将x 插入y左侧，删除操作需要一次链接，插入左侧操作需要两次链接。

link(Lx , Rx); //删除x
link(Ly , x);  //Ly 和 x 链接
link(x , y); // x 和 y 链接
1
2
3

④ 插入(将 x 插入 y 右侧)。将 x 插入 y 右侧时，先删除 x，然后将x 插入 y 右侧，删除操作需要1次链接，插入右侧操作需要两次链接。

link(Lx , Rx); //删除x
link(y , x); //将 y 和 x 链接
link(x , Ry); //将 x 和 Ry 链接
1
2
3

⑤ 交换(相邻)。将x 与 y 交换位置，如果x和y相邻且x在y右侧，则先交换x、y，统一为x 在 y 左侧处理。3次链接。

link(Lx , y); //Lx 与 y 链接
link(y , x); //y 和 x 链接
link(x , Ry); //x 和 Ry 链接
1
2
3

⑥ 交换(不相邻)。将x与y交换位置，如果x和y不相邻，则交换操作需要4次链接。

link(Lx , y); //Lx 和 y链接
link(y , Rx); //y 和 Rx 链接
link(Ly , x); //Ly 和 x 链接
link(x , Ry); // x 和 Ry链接
1
2
3
4

⑦ 翻转。如果标记了翻转，且长度 n 为 奇数，则正向奇数位之和 与 反向奇数位 之和一样。

如果如果标记了翻转，且长度 n 为 偶数，则反向奇数位之和 等于所有元素之和减去正向奇数位之和。

∴ 只需要统计正向奇数位之和，再判断翻转标记和长度是否为偶数。

【完美图解】

（1）

以输入样例为例，n =6，初始化前驱数组和后继数组

（2）

1 1 4：执行1号指令(将 1 移到 4 左侧)，先删除1，然后将1 插入 4 左侧。

即修改2的前驱为0，0的后继为2；1的前驱为1，3的后继为1；4的前驱为1，1的后继为4

（3）

2 3 5 ： 执行2 号指令(将 3 移到 5 右侧)，先删除3，然后将3 插入5 右侧。

即修改1的前驱为2，2的后继为1；3的前驱为5，5的后继为3；6的前驱为3，3的后继为6

（4）

3 1 6 ：执行交换(不相邻) 指令，1 和 6 不相邻，交换要4次链接。

即修改4个链接：6的前驱为2，2的后继为6；4的前驱为6，6的后继为4；1的前驱为3，3的后继为1；0的前驱为1，1的后继为0。

（5）

4 ： 执行翻转指令，标记翻转 flag = true。

（6）

如果n 为偶数且翻转为真，则反向奇数位之和等于所有数之和减去正向奇数位之和。

反向奇数位之和=所有数之和-正向奇数位之和=6×(6+1)/2-(2+4+3)=12。

所以答案 输出了12。

【算法实现】

#include
#include

using namespace std;

int r[100000 + 5], l[100000 + 5];

//初始化 
void init(int n){
	
	for(int i = 1 ; i <= n ; i++){
		
		l[i] = i - 1;
		r[i] = (i + 1) % (n + 1);
		
	}
	r[0] = 1;
	l[0] = n;
}

void link(int L, int R){
	r[L] = R;
	l[R] = L;
}

int main(){
	int n , m , a , x , y , k = 0;
	bool flag;
	
	while(cin >> n >> m){
		flag = false;
		init(n);
		for(int i = 0; i < m ; i++){
			
			cin >> a;
			if(a == 4){
				flag = !flag; //翻转标记 
			}
			else{
				
				cin >> x >> y;
				if(a == 3 && r[y] == x){
					swap(x , y);
				}
				if(a != 3 && flag){
					a = 3 - a;
				}
				if(a == 1 && x == l[y]){
					continue;
				}
				if(a == 2 && x == r[y]){
					continue;
				}
				int Lx = l[x] , Rx = r[x] , Ly = l[y] , Ry = r[y];
				if(a == 1){
					link(Lx , Rx); //删除x
					link(Ly,x);
					link(x,y);//x插入y左 
				}
				else if(a == 2){
					link(Lx,Rx);//删除x 
					link(y,x);
					link(x,Ry);//x插入y右	
				}
				else if(a == 3){
					if(r[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 t = 0;
		
		long long sum = 0;
		
		for(int i = 1; i <= n ; i++){
			
			t = r[t];
			if(i % 2 == 1){
				sum += t;
			}
		}
		if(flag && n % 2 == 0){
			
			sum = (long long) n * (n + 1) / 2 - sum;
		}
		cout << "Case " << ++k << ": " << sum << endl;
	}
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

就不交了，也交不上去。

跑一下用例

OK。