当前位置 博文首页 > 可惜浅灰的博客：静态链表应用：UVA12657 移动盒子
题目描述：
? ? 你有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
输入
最多有10组数据，每个数据会包含两个整数n,m（1≤n,m<100,000）, 接下来是m行数据，表示操作。
输出
对于每组数据，输出他们奇数位置的编号的和。
解题思路：
? ? 1、需要通过下标找到元素，适合用数组；而元素的移动又有插入和删除操作，适合用链表；故此题适合使用静态链表；
? ? 2、在静态链表中的插入和删除操作都需要通过连接两个节点来操作实现；
? ? 3、线性表的翻转操作会使时间复杂度暴涨，做题只需要要能应付输出即可，没必要真的将真个线性表翻转。
? ? 4、通过一个bool的变量，标记线性表的正向和反向，反向时注意左右互换。
代码实现：
/*
2021年8月29日10:00:11
*/
#include <iostream>
using namespace std;
#define max_size 100000
int l[max_size], r[max_size]; //前驱数组，后继数组
void Init(const int& n)
{
for (int i = 1; i <= n; i++)
{
l[i] = i - 1; //前驱数组中，内容是下标的前驱
r[i] = (i + 1) % (n + 1); //后继数组中，内容是下标的后继
}
l[0] = n;
r[0] = 1;
}
void Link(int x, int y) //在链表中连接两个结点
{
l[y] = x; //y的前驱是x
r[x] = y; //x的后继是y
}
void Solve(const int& m, bool& turn)
{
int x = 0, y = 0;
for(int i = 0; i < m; i++)
{
//cout << "for num" << i << endl;
int opt = 0;
cin >> opt;
if (opt == 4)
{
turn = !turn;
continue;
}
cin >> x >> y;
if (turn && (opt == 1 || opt == 2)) //翻转过之后，左右变了
{
opt = 3 - opt;
}
int ly = l[y], ry = r[y], lx = l[x], rx = r[x];
if (opt == 1)
{
if (ly == x)
{
continue;
}
else
{
Link(lx, rx); //从链表上删掉x
Link(ly, x);
Link(x, y); //xy连接,x在y的左侧
}
}
else if (opt == 2)
{
if (ry == x)
{
continue;
}
else
{
Link(lx, rx); //从链表上删掉x
Link(y, x);
Link(x, ry); //xy连接,x在y的右侧
}
}
else if (opt == 3)
{
if (r[x] == y) //两个挨在一起
{
Link(lx, y);
Link(y, x);
Link(x, ry);
}
else if (l[x] == y)
{
Link(ly, x);
Link(x, y);
Link(y, rx);
}
else
{
Link(lx, y);
Link(y, rx);
Link(ly, x);
Link(x, ry);
}
}
}
//cout << "for end" << endl;
}
void Output(int& n, const bool& turn, const int& case_num)
{
int temp = 0;
long long sum = 0;
for (int i = 1; i <= n; i++) //奇数位加和
{
temp = r[temp];
if (i % 2 == 1)
{
sum += temp;
}
}
if (turn && n % 2 == 0) //翻转了
{
//奇数个翻转还好，偶数个翻转就要奇数位和偶数位对调
sum = (long long)(1 + n) * n / 2 - sum;
}
cout << "Case " << case_num << ": " << sum << endl;
}
int main()
{
int n = 0, m = 0;
int case_num = 1;
while (cin >> n >> m)
{
bool turn = false; //记录是否翻转
Init(n);
Solve(m, turn);
Output(n, turn, case_num);
case_num++;
}
return 0;
}